oj.uz

Submission #807701

# Submission time Handle Problem Language Result Execution time Memory
807701 2023-08-04T22:01:49 Z AndiR Solar Storm (NOI20_solarstorm) C++14
25 / 100
 454 ms 145724 KB 
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
const int Nmax=1000000;

int n, s, k, d[Nmax], v[Nmax], r[Nmax];
int st[Nmax+1], sol;
ll spd[Nmax], spv[Nmax], mx;

vector <int >ad[Nmax+1];
ll dist(int a, int b){
    if (a==b)
        return 0;
    if (a==0)
        return spd[b-1];
    return spd[b-1]-spd[a-1];
}
ll vp(int a, int b){
    if (a==0)
        return spv[b];
    return spv[b]-spv[a-1];
}
void dfs(int nod, int lev){
    st[lev]=nod;
    if (nod!=n){
        int l;
        if (lev<s)
            l=n-1;
        else l=st[lev-s]-1;
        //cout<<nod<<' '<<l<<'\n';
        if (vp(nod, l)>mx){
            mx=vp(nod, l);
            sol=nod;
        }
    }
    for (int i=0; i<ad[nod].size(); i++)
        dfs(ad[nod][i], lev+1);
}
int main()
{
    cin>>n>>s>>k;
    for (int i=0; i<n-1 ;i++)
        cin>>d[i];
    for (int i=0; i<n; i++)
        cin>>v[i];
    spd[0]=d[0];
    for (int i=1; i<n-1; i++)
        spd[i]=spd[i-1]+d[i];
    spv[0]=v[0];
    for (int i=1; i<n; i++)
        spv[i]=spv[i-1]+v[i];
    ///cautam cel mai din dreapta modul din intervalul k
    int p1=0;
    for (int i=0; i<n; i++)
        while (dist(p1, i)>k)
            r[p1++]=i-1;
    for (int i=p1; i<n; i++)
        r[i]=n-1;
    ///cream arborele
    for (int i=0; i<n; i++)
        ad[r[r[i]]+1].push_back(i);
    dfs(n, 0);
    cout<<s<<'\n';
    for (int i=0; i<s; i++){
        //cout<<sol<<' ';
        if (sol==n)
            cout<<n<<' ';
        else{
            cout<<r[sol]+1<<' ';
            sol=r[r[sol]]+1;
        }
    }
    return 0;
}

Compilation message

SolarStorm.cpp: In function 'void dfs(int, int)':
SolarStorm.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i=0; i<ad[nod].size(); i++)
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23796 KB Output is correct
2 Correct 14 ms 24796 KB Output is correct
3 Correct 17 ms 24956 KB Output is correct
4 Correct 13 ms 24256 KB Output is correct
5 Correct 11 ms 23836 KB Output is correct
6 Correct 14 ms 24092 KB Output is correct
7 Correct 15 ms 24156 KB Output is correct
8 Correct 15 ms 24332 KB Output is correct
9 Correct 14 ms 24116 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Correct 16 ms 24316 KB Output is correct
12 Correct 13 ms 24276 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 44844 KB Output is correct
2 Correct 236 ms 48528 KB Output is correct
3 Correct 229 ms 59176 KB Output is correct
4 Correct 267 ms 66680 KB Output is correct
5 Correct 364 ms 74224 KB Output is correct
6 Correct 419 ms 91272 KB Output is correct
7 Correct 286 ms 79196 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23796 KB Output is correct
2 Correct 14 ms 24796 KB Output is correct
3 Correct 17 ms 24956 KB Output is correct
4 Correct 13 ms 24256 KB Output is correct
5 Correct 11 ms 23836 KB Output is correct
6 Correct 14 ms 24092 KB Output is correct
7 Correct 15 ms 24156 KB Output is correct
8 Correct 15 ms 24332 KB Output is correct
9 Correct 14 ms 24116 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Correct 16 ms 24316 KB Output is correct
12 Correct 13 ms 24276 KB Output is correct
13 Correct 40 ms 44844 KB Output is correct
14 Correct 236 ms 48528 KB Output is correct
15 Correct 229 ms 59176 KB Output is correct
16 Correct 267 ms 66680 KB Output is correct
17 Correct 364 ms 74224 KB Output is correct
18 Correct 419 ms 91272 KB Output is correct
19 Correct 286 ms 79196 KB Output is correct
20 Incorrect 31 ms 38656 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 122336 KB Output is correct
2 Correct 228 ms 83484 KB Output is correct
3 Correct 242 ms 88152 KB Output is correct
4 Correct 344 ms 116888 KB Output is correct
5 Correct 325 ms 114040 KB Output is correct
6 Correct 359 ms 119360 KB Output is correct
7 Correct 454 ms 145724 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23796 KB Output is correct
2 Correct 14 ms 24796 KB Output is correct
3 Correct 17 ms 24956 KB Output is correct
4 Correct 13 ms 24256 KB Output is correct
5 Correct 11 ms 23836 KB Output is correct
6 Correct 14 ms 24092 KB Output is correct
7 Correct 15 ms 24156 KB Output is correct
8 Correct 15 ms 24332 KB Output is correct
9 Correct 14 ms 24116 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Correct 16 ms 24316 KB Output is correct
12 Correct 13 ms 24276 KB Output is correct
13 Incorrect 11 ms 24168 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23796 KB Output is correct
2 Correct 14 ms 24796 KB Output is correct
3 Correct 17 ms 24956 KB Output is correct
4 Correct 13 ms 24256 KB Output is correct
5 Correct 11 ms 23836 KB Output is correct
6 Correct 14 ms 24092 KB Output is correct
7 Correct 15 ms 24156 KB Output is correct
8 Correct 15 ms 24332 KB Output is correct
9 Correct 14 ms 24116 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Correct 16 ms 24316 KB Output is correct
12 Correct 13 ms 24276 KB Output is correct
13 Correct 40 ms 44844 KB Output is correct
14 Correct 236 ms 48528 KB Output is correct
15 Correct 229 ms 59176 KB Output is correct
16 Correct 267 ms 66680 KB Output is correct
17 Correct 364 ms 74224 KB Output is correct
18 Correct 419 ms 91272 KB Output is correct
19 Correct 286 ms 79196 KB Output is correct
20 Incorrect 31 ms 38656 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23796 KB Output is correct
2 Correct 14 ms 24796 KB Output is correct
3 Correct 17 ms 24956 KB Output is correct
4 Correct 13 ms 24256 KB Output is correct
5 Correct 11 ms 23836 KB Output is correct
6 Correct 14 ms 24092 KB Output is correct
7 Correct 15 ms 24156 KB Output is correct
8 Correct 15 ms 24332 KB Output is correct
9 Correct 14 ms 24116 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Correct 16 ms 24316 KB Output is correct
12 Correct 13 ms 24276 KB Output is correct
13 Correct 40 ms 44844 KB Output is correct
14 Correct 236 ms 48528 KB Output is correct
15 Correct 229 ms 59176 KB Output is correct
16 Correct 267 ms 66680 KB Output is correct
17 Correct 364 ms 74224 KB Output is correct
18 Correct 419 ms 91272 KB Output is correct
19 Correct 286 ms 79196 KB Output is correct
20 Incorrect 31 ms 38656 KB Output isn't correct
21 Halted 0 ms 0 KB -