# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
114184 | 2019-05-31T08:25:29 Z | patrikpavic2 | 수열 (APIO14_sequence) | C++17 | 2000 ms | 89592 KB |
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <vector> #include <set> #include <map> #include <queue> #include <algorithm> #include <algorithm> #include <deque> #define X first #define Y second #define PB push_back using namespace std; typedef long long ll; typedef pair < ll, ll > pll; const int N = 1e5 + 500; const int K = 215; inline ll ccw(const pll &A, const pll &B, const pll &C){ return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y); } int ind[N]; pll hl[N]; int cur = 0, n, k; ll P[N], lst[N], dp[N], a[N]; int rek[N][K], cur_k, sz; inline void add(const pll &X,const int &i){ for(;sz > 2 && ccw(X, hl[sz - 1], hl[sz - 2]) <= 0LL; sz--); hl[sz] = X; ind[sz++] = i; cur = min(cur, sz - 1); } inline ll get(const int &i,const ll &x){ return hl[i].X * x + hl[i].Y; } inline int query(const ll &x){ if(sz == 0) return -1; for(; cur + 1 < sz && get(cur, x) < get(cur + 1, x); cur++); return cur; } inline void dinamika(){ sz = 0; cur = 0; for(int i = 0;i < n;i++){ int r = query(P[i]); dp[i] = -1; if(r >= 0){ rek[i][cur_k] = ind[r]; dp[i] = get(r, P[i]); } if(lst[i] >= 0) add({P[i], lst[i] - P[i] * P[i]}, i); lst[i] = dp[i]; } cur_k++; } int main(){ scanf("%d%d", &n, &k); for(int i = 0;i < n;i++){ scanf("%d", a + i); P[i] = a[i] + (i ? P[i - 1] : 0); } for(int i = 0;i < k;i++) dinamika(); printf("%lld\n", dp[n - 1]); vector < int > fin; int cur = n - 1; for(int i = k - 1;i >= 0;i--){ fin.PB(rek[cur][i]); cur = fin.back(); } reverse(fin.begin(), fin.end()); for(int x : fin) printf("%d ", x + 1); printf("\n"); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 512 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 999 == 999 |
3 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 0 == 0 |
4 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 1542524 == 1542524 |
5 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 4500000000 == 4500000000 |
6 | Incorrect | 2 ms | 384 KB | contestant didn't find the optimal answer: 0 < 1 |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 1093956 == 1093956 |
2 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 302460000 == 302460000 |
3 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 122453454361 == 122453454361 |
4 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 93663683509 == 93663683509 |
5 | Incorrect | 2 ms | 384 KB | contestant didn't find the optimal answer: 1005301269 < 1005304678 |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 512 KB | contestant didn't find the optimal answer: 407161746 < 610590000 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 1280 KB | contestant didn't find the optimal answer: 20166072 < 21503404 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 9216 KB | contestant found the optimal answer: 1818678304 == 1818678304 |
2 | Correct | 10 ms | 9216 KB | contestant found the optimal answer: 1326260195 == 1326260195 |
3 | Correct | 77 ms | 9344 KB | contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
4 | Correct | 10 ms | 9216 KB | contestant found the optimal answer: 3748491676694116 == 3748491676694116 |
5 | Incorrect | 53 ms | 9216 KB | contestant didn't find the optimal answer: 1077516459 < 1085432199 |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 124 ms | 89232 KB | contestant found the optimal answer: 19795776960 == 19795776960 |
2 | Correct | 130 ms | 89304 KB | contestant found the optimal answer: 19874432173 == 19874432173 |
3 | Execution timed out | 2045 ms | 89592 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |