oj.uz

Submission #621250

# Submission time Handle Problem Language Result Execution time Memory
621250 2022-08-03T15:37:50 Z PoonYaPat Lightning Rod (NOI18_lightningrod) C++14
11 / 100
 1573 ms 232972 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX=10000005;
int n,a[MX],b[MX],pre[MX],pos[MX],dp[MX];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; ++i) {
        int x,y;
        cin>>x>>y;
        a[i]=x-y;
        b[i]=x+y;
    }

    for (int i=1; i<=n; ++i) {
        int idx=i-1;
        while (a[i]<=a[idx] && idx>=1) idx=pre[idx];
        pre[i]=idx;
    }

    for (int i=n; i>=1; --i) {
        int idx=i+1;
        while (b[i]>=b[idx] && idx<=n) idx=pos[idx];
        pos[i]=idx;
    }

    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for (int i=1; i<=n; ++i) dp[pos[i]-1]=min(dp[pos[i]-1],dp[pre[i]]+1),dp[i]=min(dp[i],dp[i-1]+1);
    cout<<dp[n];
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1573 ms 232972 KB Output is correct
2 Correct 1477 ms 231952 KB Output is correct
3 Correct 1436 ms 220700 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 39448 KB Output is correct
2 Correct 15 ms 39484 KB Output is correct
3 Correct 14 ms 39380 KB Output is correct
4 Correct 15 ms 39436 KB Output is correct
5 Correct 16 ms 39472 KB Output is correct
6 Correct 15 ms 39388 KB Output is correct
7 Correct 16 ms 39420 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 39448 KB Output is correct
2 Correct 15 ms 39484 KB Output is correct
3 Correct 14 ms 39380 KB Output is correct
4 Correct 15 ms 39436 KB Output is correct
5 Correct 16 ms 39472 KB Output is correct
6 Correct 15 ms 39388 KB Output is correct
7 Correct 16 ms 39420 KB Output is correct
8 Correct 15 ms 39380 KB Output is correct
9 Incorrect 17 ms 39380 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 39448 KB Output is correct
2 Correct 15 ms 39484 KB Output is correct
3 Correct 14 ms 39380 KB Output is correct
4 Correct 15 ms 39436 KB Output is correct
5 Correct 16 ms 39472 KB Output is correct
6 Correct 15 ms 39388 KB Output is correct
7 Correct 16 ms 39420 KB Output is correct
8 Correct 15 ms 39380 KB Output is correct
9 Incorrect 17 ms 39380 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 39448 KB Output is correct
2 Correct 15 ms 39484 KB Output is correct
3 Correct 14 ms 39380 KB Output is correct
4 Correct 15 ms 39436 KB Output is correct
5 Correct 16 ms 39472 KB Output is correct
6 Correct 15 ms 39388 KB Output is correct
7 Correct 16 ms 39420 KB Output is correct
8 Correct 15 ms 39380 KB Output is correct
9 Incorrect 17 ms 39380 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1573 ms 232972 KB Output is correct
2 Correct 1477 ms 231952 KB Output is correct
3 Correct 1436 ms 220700 KB Output is correct
4 Correct 14 ms 39448 KB Output is correct
5 Correct 15 ms 39484 KB Output is correct
6 Correct 14 ms 39380 KB Output is correct
7 Correct 15 ms 39436 KB Output is correct
8 Correct 16 ms 39472 KB Output is correct
9 Correct 15 ms 39388 KB Output is correct
10 Correct 16 ms 39420 KB Output is correct
11 Correct 15 ms 39380 KB Output is correct
12 Incorrect 17 ms 39380 KB Output isn't correct
13 Halted 0 ms 0 KB -