Submission #331521

#	Time	Username	Problem	Language	Result	Execution time	Memory
331521		limabeans	Bigger segments (IZhO19_segments)	C++17	27 / 100	114 ms	2412 KiB

segments

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;
const ll inf = 1e18;


const int maxn = 505;



int n;
ll a[maxn];
ll dp[maxn][maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }

    for (int i=0; i<=n; i++) {
	for (int j=0; j<=n; j++) {
	    dp[i][j] = inf;
	}
    }

    dp[0][0] = 0;
    for (int i=1; i<=n; i++) {
	for (int j=1; j<=i; j++) {
	    ll sum = 0;
	    for (int k=i; k>=1; k--) {
		sum += a[k];
		if (dp[k-1][j-1] <= sum) {
		    dp[i][j] = min(dp[i][j], sum);
		}
	    }
	}
    }

    int res = 0;
    for (int j=1; j<=n; j++) {
	if (dp[n][j]<inf) res = j;
    }

    cout<<res<<endl;    
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27