# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
114169 | 2019-05-31T07:48:40 Z | patrikpavic2 | 수열 (APIO14_sequence) | C++17 | 2000 ms | 86628 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 = 205; ll ccw(pll A, pll B, pll C){ return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y); } vector < int > ind; vector < pll > hl; int cur = 0, n, k; ll P[N], lst[N], dp[N], a[N]; int rek[N][K], cur_k; void add(pll X, int i){ for(;hl.size() >= 2 && ccw(X, hl.back(), hl[hl.size() - 2]) <= 0; hl.pop_back(), ind.pop_back()); hl.PB(X); ind.PB(i); cur = min(cur, (int)hl.size() - 1); } ll get(int i, ll x){ if(i < 0) return i; return hl[i].X * x + hl[i].Y; } int query(ll x){ if(hl.size() == 0) return -1; for(; cur + 1 < hl.size() && get(cur, x) <= get(cur + 1, x); cur++); return cur; } void precompute(){ for(int i = 0;i < n;i++){ P[i] = a[i] + (i ? P[i - 1] : 0); } } void dinamika(){ hl.clear(); ind.clear(); cur = 0; for(int i = 0;i < n;i++){ int r = query(P[i]); 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]; //printf("%lld ", dp[i]); } cur_k++; //printf("\n"); } int main(){ scanf("%d%d", &n, &k); for(int i = 0;i < n;i++) scanf("%d", a + i); precompute(); 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 | 1 ms | 384 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 999 == 999 |
3 | Correct | 1 ms | 384 KB | contestant found the optimal answer: 0 == 0 |
4 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 1542524 == 1542524 |
5 | Incorrect | 2 ms | 384 KB | position 1 occurs twice in split scheme |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | contestant found the optimal answer: 1093956 == 1093956 |
2 | Incorrect | 2 ms | 464 KB | position 1 occurs twice in split scheme |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 512 KB | contestant found the optimal answer: 610590000 == 610590000 |
2 | Incorrect | 2 ms | 512 KB | position 1 occurs twice in split scheme |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1280 KB | contestant found the optimal answer: 21503404 == 21503404 |
2 | Incorrect | 3 ms | 1152 KB | position 1 occurs twice in split scheme |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8960 KB | contestant found the optimal answer: 1818678304 == 1818678304 |
2 | Correct | 10 ms | 8984 KB | contestant found the optimal answer: 1326260195 == 1326260195 |
3 | Correct | 135 ms | 8956 KB | contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
4 | Correct | 10 ms | 9212 KB | contestant found the optimal answer: 3748491676694116 == 3748491676694116 |
5 | Incorrect | 68 ms | 8960 KB | position 1 occurs twice in split scheme |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 102 ms | 85792 KB | contestant found the optimal answer: 19795776960 == 19795776960 |
2 | Correct | 99 ms | 85992 KB | contestant found the optimal answer: 19874432173 == 19874432173 |
3 | Execution timed out | 2045 ms | 86628 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |