oj.uz

Submission #764885

# Submission time Handle Problem Language Result Execution time Memory
764885 2023-06-24T06:17:13 Z dxz05 Parkovi (COCI22_parkovi) C++17
0 / 110
 99 ms 9824 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 = 2e14;
    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;
        }
    }

    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:80:13: warning: unused variable 'startTime' [-Wunused-variable]
   80 |     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 36 ms 1024 KB Output is correct
2 Correct 47 ms 984 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 1064 KB Output is correct
2 Correct 44 ms 5244 KB Output is correct
3 Correct 41 ms 5004 KB Output is correct
4 Correct 43 ms 4948 KB Output is correct
5 Correct 90 ms 9824 KB Output is correct
6 Correct 86 ms 7124 KB Output is correct
7 Correct 93 ms 7664 KB Output is correct
8 Correct 43 ms 4804 KB Output is correct
9 Correct 47 ms 4724 KB Output is correct
10 Correct 45 ms 4596 KB Output is correct
11 Correct 39 ms 4484 KB Output is correct
12 Incorrect 99 ms 8160 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 -