Submission #1002859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002859		hyakup	Cigle (COI21_cigle)	C++17	48 / 100	77 ms	4692 KiB

cigle

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;
#define pii pair<int, int> 


const int inf = 1e9 + 10; 
const int maxn = 500 + 10; 
const int maxm = 3e7 + 10; 

vector<int> v( maxn ); 

ll dp[maxn][maxn];
bool marc[maxm];  

int main(){
    int n; cin >> n; 
    for( int i = 1; i <= n; i++ ) cin >> v[i]; 
    ll resp = 0; 
    for( int a = 1; a <= n; a++){
        for( int b = 1; b < a; b++ ){
            int sum = 0; 
            for( int i = b + 1; i < a; i++ ){
                sum += v[i]; 
                marc[sum] = true; 
            }
            sum = 0; 
            ll& ans = dp[a][b]; 
            int cont = 0; 
            for( int c = b - 1; c >= 0; c-- ){
                if( marc[sum] ) cont++; 
                sum += v[c + 1];
                ans = max( ans, dp[b][c] + cont ); 
            } 
            sum = 0; 
            for( int i = b + 1; i < a; i++ ){
                sum += v[i]; 
                marc[sum] = false; 
            }
            resp = max( resp, ans ); 
        }
    }
    cout << resp << endl;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 0 / 52