Submission #1693844


Source Code Expand

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね

//ここから編集する


int main() {
    int N;
    cin >> N;
    vector<vector<bool> > flag(N, vector<bool>(N, false));
    vector<int> a(N);
    vector<int> pos(N + 1);

    REP(i, 0, N) {
        cin >> a[i];
        pos[a[i]] = i;
    }

    set<int> set1;
    set<int> rset;
//    set1.insert(-1);
    set1.insert(N);
    rset.insert(1);

    ll ans = 0;

    for (int i = 1; i <= N; i++) {
        set1.insert(pos[i]);
        rset.insert(-pos[i]);
        auto itA = rset.upper_bound(-pos[i]);
        auto itB = set1.upper_bound(pos[i]);
//        printf("i = %d,*itA = %d,*itB = %d\n", i, -*itA, *itB);
        ans += i * (pos[i] + *itA) * (*itB - pos[i]);
    }

    cout << ans << endl;


    return 0;
}

Submission Info

Submission Time
Task B - Minimum Sum
User homesentinel
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2093 Byte
Status TLE
Exec Time 3880 ms
Memory 1908 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 7
TLE × 6
Set Name Test Cases
Sample example0, example1, example2
All corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2
Case Name Status Exec Time Memory
corner0 TLE 2159 ms -642764 KB
corner1 TLE 2215 ms -642448 KB
corner2 AC 12 ms 1780 KB
corner3 TLE 3880 ms -642336 KB
example0 AC 12 ms 1780 KB
example1 AC 1 ms 256 KB
example2 AC 1 ms 256 KB
maxrand0 TLE 2493 ms -642452 KB
maxrand1 TLE 2884 ms -642180 KB
maxrand2 TLE 2508 ms -642436 KB
rand0 AC 12 ms 1908 KB
rand1 AC 1 ms 256 KB
rand2 AC 2 ms 256 KB