제출 #32102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32102		RezwanArefin01	수열 (APIO14_sequence)	C++14	71 / 100	2000 ms	86784 KiB

sequence

    #include <bits/stdc++.h>
    using namespace std;
     
    const int MAX = 100005;
    typedef long long ll;
    typedef pair<ll, ll> pll;
     
     
    #define f first
    #define s second
     
     
    pll line[MAX];
    int orig[MAX];
    int ct = 0;
    int ptr = 0;
    bool bad(pll l0, pll l1, pll l2) {
    	return (l1.s-l0.s)*(l0.f-l2.f) >= (l0.f-l1.f)*(l2.s-l0.s);
    }
     
    ll f(pll l, ll x) {
    	return l.f * x + l.s;
    }
    void add(pll l, int i) {
    	while (ct >= 2 && ptr < ct && bad(line[ct-1], line[ct], l)) {
    		ct--;
    	}
    	ptr = min(ptr, ct);
    	ct++;
    	line[ct] = l;
    	orig[ct] = i;
    }
     
    pair<ll, int> get(ll x) {
    	ptr = max(ptr, 1);
    	ptr = min(ptr, ct - 1);
    	if (ct == 0) { return {0, 0}; }
    	while (ptr < ct && f(line[ptr], x) < f(line[ptr+1], x)) {
    		ptr++;
    	}
    	return {f(line[ptr], x), orig[ptr]};
    }
     
    int a[MAX];
    ll p[MAX];
    ll dp[MAX][2];
    int last[MAX][205];
    int main() {
    	// double c = clock();
    	//freopen("a.in", "r", stdin);
    	//freopen("a.out", "w", stdout);
     
    	int n, k0; scanf("%d %d", &n, &k0);
    	for (int i=1; i<=n; i++) {
    		scanf("%d", &a[i]); 
    		p[i] = (ll)p[i-1] + (ll)a[i];
    	}
    	for (int k=1; k<=k0+1; k++) {
    		ct = 0; int kk = k % 2;
    		for (int i=k-1; i<=n; i++) {
    			if (k == 1) { 
    				dp[i][kk] = 0;
    			}
    			else {
    				add({p[i], (ll)dp[i][kk ^ 1]-(ll)p[i]*(ll)p[i]}, i);
    				if (i != k-1) { 
    					pll ans = get(p[i]);
    					dp[i][kk] = ans.f; 
    					last[i][k] = (int)ans.s;
    				}
    			}
    		}
    	}
    	k0++;
    	printf("%lld\n", dp[n][k0%2]);
    	while (k0 != 1) {
    		int bef = last[n][k0];
    		printf("%d ", bef);
    		n = bef; k0--;
    	}
    	// cout << (clock() - c) / (double)CLOCKS_PER_SEC;
    }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int main()':
sequence.cpp:53:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      int n, k0; scanf("%d %d", &n, &k0);
                                        ^
sequence.cpp:55:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &a[i]); 
                         ^

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29