oj.uz

Submission #1007624

# Submission time Handle Problem Language Result Execution time Memory
1007624 2024-06-25T09:28:05 Z christinelynn Lasers (NOI19_lasers) C++17
10 / 100
 38 ms 9504 KB 
#include <bits/stdc++.h>
using namespace std;

# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

bool sorting(pair<int, int> a, pair<int, int> b) {
    return a.sec > b.sec;
}

void solve() {
    int n, q; cin >> n >> q;

    int ans = 0;
    vector<pair<int, int>> range;

    while(q--) {
        // cerr << "IN" << endl;
        int x; cin >> x;
        int num[x+5];
        int pre[x+5]; pre[0] = 0;
        int suf[x+5]; suf[x+1] = n+1;
        for(int i = 1; i<=x; i++) {
            cin >> num[i];
            pre[i] = pre[i-1]+num[i]; 
        }

        int prev = 0;
        for(int i = x; i>=1; i--) suf[i] = suf[i+1]-num[i];

        for(int i = 1; i<=x; i++) {
            if(suf[i] <= pre[i]) range.pb({suf[i], pre[i]});
        }
    }

    sort(range.begin(), range.end(), sorting);

    int l = n+2; int r = n+1;
    for(auto v: range) {
        if(v.sec < r) {
            ans += r-l+1;
            r = v.sec;
        }

        l = min(l, v.fir);
    }

    ans += r-l+1;

    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

Compilation message

lasers.cpp: In function 'void solve()':
lasers.cpp:35:13: warning: unused variable 'prev' [-Wunused-variable]
   35 |         int prev = 0;
      |             ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 9504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 9504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -