chigichan24のお気持ち表明

おきもちを表明している

JOI2015本選オンラインに参加した

こんばんは.chigichanです.
テストシーズンはしなきゃいけないことが全くはかどらないですね.


ということで,後輩たちが参加していたJOI本選のオンラインに参加しました.



といっても気づいたのが,

の15分くらい前で,1問目をささっと読み始めました.



読んだ感じだと,今までの本選1問目の傾向と少し違うかなという感想でした.

普段は,強実装 or 数学 という印象でしたが,累積和だったので多少驚きました.


という感じで15分くらいで書いて,提出~(^_-)-☆



ん?





ん?






5分くらい待ちました.


50/100 WA


え?

しかし,TLEではないのでなんでやねんという感じに...




10分後くらいに気づいた.

ansの値はintを超えると....




訂正して提出~(^_-)-☆




f5押しまくって待機してたら....




503



504






(;_;



鯖落ちかよ....





そして,





時は過ぎ,











終了45分前くらい...





その後2,3は問題を読んで,

2はメモ化再帰で書くと楽そう.
3はdijkstraがんばれ♥がんばれ♥って感じという感想.







結果:1完






JOIは良問多くて良いですね~
後輩は一人春の可能性があるので彼が通ってるといいな~






コード

#include <bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={-1,0,1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-15;
#define PB push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<ll,ll> Pii;
typedef pair<Pii,Pii> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
vector < Pii > data;
ll D[100001];
ll IC[100001];
Pii cost[100001];
vector < Pii > imos;
int main(){
    int N,M;
    scanf("%d%d",&N,&M);
    rep(i,M){
        scanf("%lld",&D[i]);
        D[i]--;
    }
    rep(i,N-1){
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        cost[i] = Pii(a,b);
        IC[i] = c;
    }
    rep(i,M-1){
        ll a = min(D[i],D[i+1]);
        ll b = max(D[i],D[i+1]);
        imos.PB(Pii(a,1));
        imos.PB(Pii(b,-1));
    }
    sort(imos.begin(),imos.end());
    ll prev = -1;
    ll sum = 0;
    ll ans = 0;
    rep(i,imos.size()){
        if(prev != imos[i].fi){
            if(prev == -1){
                prev = imos[i].fi;
            }
            else{
                ll index = prev;
                while(index < imos[i].fi){
                    ans += min(cost[index].fi*sum,cost[index].se*sum+IC[index]);
                    index++;
                }
                prev = imos[i].fi;
            }
        }
        sum += imos[i].se;
    }

    printf("%lld\n",ans);
    return 0;
}

相変わらずコードが汚い...


テスト勉強しなきゃ....