oj.uz

Submission #670078

# Submission time Handle Problem Language Result Execution time Memory
670078 2022-12-08T03:05:15 Z soondro2266 Semiexpress (JOI17_semiexpress) C++14
100 / 100
 12 ms 4616 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct obj{
    int l,r,a,c,t;
    obj(int _l, int _r, int _a, int _c, int pref, int _t){
        t = _t - pref;
        l = _l;
        r = _r;
        a = _a;
        c = _c;
    }
};
signed main(){
    int n,m,k,a,b,c,t;
    int ans = 0;
    cin >> n >> m >> k >> a >> b >> c >> t;
    vector<int> arr(m);
    for(int i = 0; i < m; i++) cin >> arr[i];
    vector<obj> lab;
    for(int i = 0,l,r,pre; i <= m-2; i++){
        l = arr[i];
        r = arr[i+1];
        pre = b*(l-1);
        if(pre <= t){
            lab.push_back(obj(l, r, a, c, pre, t));
        }
    }
    int kkkkk = arr[0];
    for(int i = 1; i < m; i++){
        kkkkk = b*(arr[i]-1);
        if(kkkkk <= t){
            ans ++;
        }
    }
    vector<int> stop;
    
    for(auto it = lab.begin(); it != lab.end(); it++){
        int cnt=0;
        int i = it->l;
        int ran = it->t;
        int step = 0,newstep,nextplace;
        while(i < it->r){
            ran = it->t - c*(i-it->l);
            if(ran<0){
                break;
            }
            newstep = ran/it->a;
            nextplace = min(it->r - 1, i+newstep);
            if(i != it->l){
                stop.push_back(nextplace - i + 1);
                cnt++;
            }
            else{
                ans += (nextplace - i);
            }
            if(cnt > k-m)break;
            i = nextplace+1;
        }
    }
    sort(stop.begin(), stop.end());
    reverse(stop.begin(), stop.end());
    if((k-m) > stop.size()){
        for(auto it = stop.begin(); it != stop.end(); it++){
            ans += *it;
        }
        cout << ans << endl;
    }
    else{
        for(int i = 0; i < (k-m); i++){
            ans += stop[i];
        }
        cout << ans << endl;
    }
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:42:13: warning: unused variable 'step' [-Wunused-variable]
   42 |         int step = 0,newstep,nextplace;
      |             ^~~~
semiexpress.cpp:63:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if((k-m) > stop.size()){
      |        ~~~~~~^~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 12 ms 4616 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 9 ms 4548 KB Output is correct
30 Correct 5 ms 2504 KB Output is correct