oj.uz

Submission #13680

# Submission time Handle Problem Language Result Execution time Memory
13680 2015-02-27T13:55:42 Z gs14004 Pinball (JOI14_pinball) C++14
51 / 100
 1000 ms 30868 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lint;

struct sti{int s,e,d,x;}a[100005];

vector<int> v;
lint dpl[300005], dpu[300005];

vector<lint> dp_low[300005], dp_high[300005];

struct rmq{
    lint tree[1050000];
    int lim;
    void init(int n){
        memset(tree,0x3f,sizeof(tree));
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void add(int x, int v){
        x += lim;
        tree[x] = v;
        while(x > 1){
            x >>= 1;
            tree[x] = min(tree[2*x],tree[2*x+1]);
        }
    }
    lint query(int s, int e){
        s += lim;
        e += lim;
        lint r = 1e18;
        while(s < e){
            if(s%2 == 1) r = max(r,tree[s++]);
            if(e%2 == 0) r = max(r,tree[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) r = max(r,tree[s]);
        return r;
    }
}rmq;

int n,m;

void input(){
    scanf("%d %d",&n,&m);
    v.push_back(1);
    v.push_back(m);
    for (int i=2; i<=n+1; i++) {
        scanf("%d %d %d %d",&a[i].s,&a[i].e,&a[i].d,&a[i].x);
        v.push_back(a[i].s);
        v.push_back(a[i].e);
        v.push_back(a[i].d);
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end()) - v.begin());
    for (int i=2; i<=n+1; i++) {
        a[i].s = (int)(lower_bound(v.begin(),v.end(),a[i].s) - v.begin());
        a[i].e = (int)(lower_bound(v.begin(),v.end(),a[i].e) - v.begin());
        a[i].d = (int)(lower_bound(v.begin(),v.end(),a[i].d) - v.begin());
    }
    a[1] = {0,0,0,0};
    a[0] = {(int)v.size()-1,(int)v.size()-1,(int)v.size()-1,0};
}

int main(){
    input();
    for (int i=1; i<n+2; i++) {
        dpu[i] = 1e18;
        for (int j=0; j<i; j++) {
            if(a[j].d <= a[i].e){
                dpu[i] = min(dpu[i],dpu[j]);
            }
        }
        dpu[i] += a[i].x;
    }
    for (int i=n+1; i>=0; i--) {
        dpl[i] = 1e18;
        for (int j=i+1; j<n+2; j++) {
            if(a[j].s <= a[i].d && a[i].d <= a[j].e){
                dpl[i] = min(dpl[i],dpl[j]);
            }
        }
        dpl[i] += a[i].x;
        dpl[i] = min(dpl[i],dpu[i]);
    }
    if(dpl[1] >= 1e18) puts("-1");
    else printf("%lld",dpl[1]);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 30228 KB Output is correct
2 Execution timed out 1000 ms 30868 KB Program timed out
3 Halted 0 ms 0 KB -