oj.uz

Submission #930925

# Submission time Handle Problem Language Result Execution time Memory
930925 2024-02-20T20:06:09 Z AtabayRajabli Split the sequence (APIO14_sequence) C++17
0 / 100
 235 ms 2392 KB 
#include <bits/stdc++.h>
 
// author : a1abay
 
#define pb          push_back
#define all(v)      v.begin(), v.end()
#define int         ll
#define gcd(a, b)   __gcd(a, b)
#define lcm(a, b)   (a*b / (__gcd(a, b)))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
 
typedef long long           ll;
const int inf =             1e9 + 7;
const int inff =            1e18 + 7;
const int sz =              1e5 + 5;
using namespace             std;
 
void open(string s, string f)
{
    freopen((s + ".txt").c_str(), "r", stdin);
    freopen((f + ".txt").c_str(), "w", stdout);
}

int n, k, a[sz], p[sz];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // open("in", "out");

    cin >> n >> k;
    for(int i = 1; i <= n; i++)cin >> a[i];
    for(int i = 1; i <= n; i++)p[i] = p[i - 1] + a[i];

    set<int> splits;
    splits.insert(0);
    splits.insert(n);
    
    int ans = 0;
    vector<int> cuts;
    while(k--)
    {  
        int mx = -1, cut = -1;
        for(int i = 1; i <= n; i++)
        {
            auto it = splits.lower_bound(i);
            int l = *--it + 1, r = *++it;
            if(l > r)continue;

            int lx = p[i] - p[l - 1];
            int rx = p[r] - p[i];
            if(lx * rx > mx)
            {
                mx = lx * rx;
                cut = i;
            }
        }
        ans += mx;
        splits.insert(cut);
        cuts.pb(cut);
    }

    cout << ans << '\n';
    for(int i : cuts)cout << i << " ";
}

Compilation message

sequence.cpp: In function 'void open(std::string, std::string)':
sequence.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen((s + ".txt").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen((f + ".txt").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB contestant found the optimal answer: 108 == 108
2 Incorrect 0 ms 348 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 0 ms 348 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 348 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 0 ms 348 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 1 ms 348 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 0 ms 348 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Incorrect 1 ms 348 KB contestant didn't find the optimal answer: 1019625813 < 1019625819
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 604 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 8 ms 1884 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 7 ms 2096 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Incorrect 235 ms 2392 KB contestant didn't find the optimal answer: 497009314607795353 < 497313449256899208
4 Halted 0 ms 0 KB -