oj.uz

Submission #764891

# Submission time Handle Problem Language Result Execution time Memory
764891 2023-06-24T06:19:34 Z dxz05 Parkovi (COCI22_parkovi) C++17
0 / 110
 97 ms 5752 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
#define BIT(x, i) (((x) >> (i)) & 1)
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 2e5 + 30;

int n;
int w[N];

vector<int> parks(ll d){
    vector<int> p;

    for (int i = 1; i <= n;){
        ll x = 0;
        int j = i + 1;
        while (j <= n && x + w[j - 1] <= d){
            x += w[j - 1];
            j++;
        }
        j--;

        p.push_back(j);

        x = 0;
        while (j < n && x + w[j] <= d){
            x += w[j];
            j++;
        }

        i = j + 1;
    }

    return p;
}

void solve(){
    int k;
    cin >> n >> k;

    for (int i = 1; i < n; i++) cin >> w[i] >> w[i] >> w[i];

    vector<int> ans;

    ll l = 0, r = 2e15;
    while (l <= r){
        ll m = (l + r) >> 1;

        vector<int> p = parks(m);

        if (p.size() <= k){
            ans = p;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    assert(!ans.empty());

    cout << ++r << endl;
    for (int x : ans) cout << x << ' ';
    cout << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:65:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |         if (p.size() <= k){
      |             ~~~~~~~~~^~~~
Main.cpp: In function 'int main()':
Main.cpp:82:13: warning: unused variable 'startTime' [-Wunused-variable]
   82 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1044 KB Output is correct
2 Correct 44 ms 1064 KB Output is correct
3 Incorrect 45 ms 972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1024 KB Output is correct
2 Correct 42 ms 1120 KB Output is correct
3 Correct 40 ms 976 KB Output is correct
4 Correct 39 ms 920 KB Output is correct
5 Correct 74 ms 5660 KB Output is correct
6 Correct 97 ms 2800 KB Output is correct
7 Correct 89 ms 3756 KB Output is correct
8 Correct 41 ms 1060 KB Output is correct
9 Correct 40 ms 1100 KB Output is correct
10 Correct 41 ms 1020 KB Output is correct
11 Correct 39 ms 1036 KB Output is correct
12 Incorrect 90 ms 5752 KB Unexpected end of file - int32 expected
13 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -