oj.uz

Submission #764890

# Submission time Handle Problem Language Result Execution time Memory
764890 2023-06-24T06:19:02 Z dxz05 Parkovi (COCI22_parkovi) C++17
0 / 110
 105 ms 5872 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;
        }
    }

    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 340 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 992 KB Output is correct
2 Correct 51 ms 1068 KB Output is correct
3 Incorrect 45 ms 968 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 972 KB Output is correct
2 Correct 52 ms 992 KB Output is correct
3 Correct 41 ms 1020 KB Output is correct
4 Correct 39 ms 896 KB Output is correct
5 Correct 74 ms 5708 KB Output is correct
6 Correct 105 ms 2828 KB Output is correct
7 Correct 89 ms 3752 KB Output is correct
8 Correct 48 ms 988 KB Output is correct
9 Correct 45 ms 972 KB Output is correct
10 Correct 41 ms 1040 KB Output is correct
11 Correct 48 ms 956 KB Output is correct
12 Incorrect 89 ms 5872 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 340 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -