oj.uz

Submission #970737

# Submission time Handle Problem Language Result Execution time Memory
970737 2024-04-27T07:44:02 Z Gangsta Split the sequence (APIO14_sequence) C++14
0 / 100
 5 ms 2652 KB 
/*
ID: didarco1
TASK: 
LANG: c++17
*/
#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define sz size()

const int N = 2e5 + 1;

using namespace std;

ll a[N], p[N], ans, n, k;

set <pii> s;

vector <int> bol;

vector <int> v;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
    	cin >> a[i];
    	p[i] = p[i-1] + a[i];
    }
    s.insert({1,n});
    while(k--){
    	ll mx = 0;
    	int bol, poz, poz1;
    	for(auto i: s){
    		for(int j = i.ff; j < i.ss; j++){
    			ll san = p[j] - p[i.ff-1], san1 = p[i.ss] - p[j];
    			if(san * san1 >= mx){
    				mx = san * san1;
    				bol = j;
    				poz = i.ff;
    				poz1 = i.ss;
    			}
    		}
    	}
    	ans += mx;
    	s.erase({poz,poz1});
    	s.insert({poz,bol});
    	s.insert({bol+1,poz1});
    	v.pb(bol);
    }
    cout << ans << '\n';
    for(auto i : v) cout << i << ' ';
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB contestant found the optimal answer: 108 == 108
2 Incorrect 1 ms 2392 KB contestant didn't find the optimal answer: 951 < 999
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB contestant didn't find the optimal answer: 1093726 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 2396 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 1 ms 2396 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 2396 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 1 ms 2396 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 1 ms 2396 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 1 ms 2396 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Incorrect 1 ms 2396 KB contestant didn't find the optimal answer: 193235243 < 193556962
9 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB contestant didn't find the optimal answer: 21419072 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB contestant didn't find the optimal answer: 1794250000 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2652 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Incorrect 5 ms 2648 KB contestant didn't find the optimal answer: 19874432171 < 19874432173
3 Halted 0 ms 0 KB -