Submission #13678

#	Time	Username	Problem	Language	Result	Execution time	Memory
13678		gs14004	Pinball (JOI14_pinball)	C++14	51 / 100	1000 ms	25028 KiB

pinball

#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=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=i; 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=i; 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]);
        }
    }
    if(dp_low[0][0] >= 1e18) puts("-1");
    else printf("%lld",dp_low[0][0]);
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49