Submission #321936

#	Time	Username	Problem	Language	Result	Execution time	Memory
321936		techiehere08	Lasers (NOI19_lasers)	C++14	87 / 100	477 ms	31980 KiB

lasers

#include<bits/stdc++.h>

using namespace std;

int main(){
  int l, r;
  cin >> l >> r;
  if(l > (int)1e6){
    int ans = 0, max = 0;
    for(int i = 0; i < r; i++){
      int n; cin >> n;
      int x, sum = 0;
      while(n--){
        cin >> x;
        sum += x;
      }
      if(max < sum) max = sum;
    }
    ans = 2 * max - l;
    if(ans < 0) ans = 0;
    cout << ans << endl;
    return 0;
  }
  int ans = 0;
  vector < vector < int >> v(r);
  for(int i = 0; i < r; i++){
    int n; cin >> n;
    v[i].push_back(0);
    while(n--){
      int x; cin >> x;
      x += v[i].back();
      v[i].push_back(x);
    }
  }
  for(int i = 1; i <= l; i++){
    bool ok = true;
    for(int j = 0; j < r; j++){
      int sum1 = 0, sum2 = 0;
      int idx = lower_bound(v[j].begin(), v[j].end(), i) - v[j].begin();
      idx--;
      sum2 = v[j].back() - v[j][idx];
      if(l - i < sum2){
        ok = false;
      }
      if(!ok) {
        //cout << "break for " << i << " " << j << endl;
        break;
      }
    }
    if(ok) ans++;
  }
  cout << l - ans << endl;
  return 0;
}

Compilation message (stderr)

lasers.cpp: In function 'int main()':
lasers.cpp:38:11: warning: unused variable 'sum1' [-Wunused-variable]
   38 |       int sum1 = 0, sum2 = 0;
      |           ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 0 / 13