oj.uz

Submission #13677

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

struct sti{int s,e,d,x;}a[100005];
struct sti2{int end, dest, cost, hi;};

bool cmp(sti2 a, sti2 b){return a.hi < b.hi;}

vector<int> v;
vector<sti2> pan[300005];
vector<lint> dp_low[300005], dp_high[300005];

int n,m;

void input(){
    scanf("%d %d",&n,&m);
    v.push_back(1);
    v.push_back(m);
    for (int i=1; i<=n; 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=1; i<=n; 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());
    }
    pan[0].push_back({0,0,0,0});
    pan[v.size()-1].push_back({(int)v.size()-1,(int)v.size()-1,0,0});
    for (int i=1; i<=n; i++) {
        pan[a[i].s].push_back({a[i].e,a[i].d,a[i].x,i});
    }
    for (int i=0; i<v.size(); i++) {
        sort(pan[i].begin(),pan[i].end(),cmp);
        dp_low[i].resize(pan[i].size());
        dp_high[i].resize(pan[i].size());
    }
}

int main(){
    input();
    int l = (int)v.size();/*
    for (int i=0; i<l; i++) {
        printf("pan debug %d\n",i);
        for (int j=0; j<pan[i].size(); j++) {
            printf("%d %d %d\n",pan[i][j].dest,pan[i][j].end,pan[i][j].cost);
        }
        puts("");
    }*/
    for (int i=l-1; i>=0; i--) {
        for (int j=0; j<pan[i].size(); j++) {
            dp_high[i][j] = 1e18;
            if(i == l-1 && j == 0){
                dp_high[i][j] = 0;
            }
            for (int k=0; k<j; k++) {
                if(pan[i][k].dest <= pan[i][j].end){
                    dp_high[i][j] = min(dp_high[i][j],dp_high[i][k]);
                }
            }
            for (int k=i+1; k<l; k++) {
                for (int m=0; m<pan[k].size(); m++) {
                    if(pan[k][m].hi >= pan[i][j].hi) continue;
                    if(pan[k][m].dest > pan[i][j].end) continue;
                    dp_high[i][j] = min(dp_high[i][j],dp_high[k][m]);
                }
            }
            dp_high[i][j] += pan[i][j].cost;
        }
    }
    for (int i=l-1; i>=0; i--) {
        for (int j=(int)pan[i].size()-1; j>=0; j--) {
            dp_low[i][j] = 1e18;
            for (int k=j+1; k<pan[i].size(); k++) {
                if(pan[i][j].dest <= pan[i][k].end){
                    dp_low[i][j] = min(dp_low[i][j],dp_low[i][k]);
                }
            }
            for (int k=i+1; k<l; k++) {
                for (int m=0; m<pan[k].size(); m++) {
                    if(pan[k][m].hi <= pan[i][j].hi) continue;
                    if(k <= pan[i][j].dest && pan[i][j].dest <= pan[k][m].end){
                        dp_low[i][j] = min(dp_low[i][j],dp_low[k][m]);
                    }
                }
            }
            dp_low[i][j] += pan[i][j].cost;
            dp_low[i][j] = min(dp_low[i][j],dp_high[i][j]);
        }
    }/*
    for (int i=0; i<l; i++) {
        printf("high debug %d\n",i);
        for (int j=0; j<pan[i].size(); j++) {
            printf("%lld\n",dp_high[i][j]);
        }
        puts("");
    }
    for (int i=0; i<l; i++) {
        printf("low debug %d\n",i);
        for (int j=0; j<pan[i].size(); j++) {
            printf("%lld\n",dp_low[i][j]);
        }
        puts("");
    }*/
    if(dp_low[0][0] >= 1e18) puts("-1");
    else printf("%lld",dp_low[0][0]);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24240 KB Output is correct
2 Correct 0 ms 24240 KB Output is correct
3 Correct 24 ms 24240 KB Output is correct
4 Correct 6 ms 24240 KB Output is correct
5 Correct 26 ms 24240 KB Output is correct
6 Correct 16 ms 24240 KB Output is correct
7 Correct 13 ms 24240 KB Output is correct
8 Correct 22 ms 24240 KB Output is correct
9 Correct 14 ms 24240 KB Output is correct
10 Correct 25 ms 24240 KB Output is correct

Subtask #4
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 25028 KB Program timed out
2 Halted 0 ms 0 KB -