#1959126

Solution for 2312: Magical Girl Sayaka-chan by btk

Source Code Status Test Cases
    Policy: public     Reviewed: 63    
00.05 sec    3644 KB    41 lines     857 bytes    2016-08-11 19:06
#include<bits/stdc++.h>

using namespace std;

struct I{I(){ios::sync_with_stdio(false);cin.tie(0);}}init;

typedef long long LL;
typedef vector<LL> V;
const LL INF=1e17;
int main(){
    int N,M,L;
    cin>>N>>M>>L;
    V onp(N);
    V sum(M+1,0);
    for(auto &it:onp)cin>>it;
    for(int i=1;i<=M;i++){
        cin>>sum[i];
        sum[i]+=sum[i-1];
    }
    sort(onp.begin(),onp.end());
    auto f=[&](int a,int b){
        return (sum[b]-sum[a-1])/L;
    };
    V dp(1,f(onp[0],onp[1]));
    for(int i=2;i<N;i++){
        V nxt(i,INF);
        for(int j=0;j<i-1;j++){
            nxt[j]=min(nxt[j],dp[j]+f(onp[i-1],onp[i]));
            nxt[i-1]=min(nxt[i-1],dp[j]+f(onp[j],onp[i]));
        }
        swap(dp,nxt);
    }
    LL res=INF;
    for(int i=0;i<N-1;i++)
        res=min(res,dp[i]+f(onp[i],onp.back()));
    cout<<res<<endl;

    return 0;
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 41/41 C++14 CPU: 00.05 sec Memory: 3644 KB Length: 857 B 2016-08-11 19:06 2016-08-11 19:06
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.00 sec 3136 KB
Case #2: : Accepted 00.00 sec 3116 KB
Case #3: : Accepted 00.00 sec 3104 KB
Case #4: : Accepted 00.00 sec 3104 KB
Case #5: : Accepted 00.00 sec 3156 KB
Case #6: : Accepted 00.00 sec 3100 KB
Case #7: : Accepted 00.00 sec 3292 KB
Case #8: : Accepted 00.00 sec 3400 KB
Case #9: : Accepted 00.00 sec 3248 KB
Case #10: : Accepted 00.00 sec 3284 KB
Case #11: : Accepted 00.00 sec 3168 KB
Case #12: : Accepted 00.00 sec 3148 KB
Case #13: : Accepted 00.00 sec 3232 KB
Case #14: : Accepted 00.00 sec 3208 KB
Case #15: : Accepted 00.00 sec 3136 KB
Case #16: : Accepted 00.00 sec 3300 KB
Case #17: : Accepted 00.00 sec 3256 KB
Case #18: : Accepted 00.04 sec 3416 KB
Case #19: : Accepted 00.04 sec 3492 KB
Case #20: : Accepted 00.03 sec 3456 KB
Case #21: : Accepted 00.03 sec 3416 KB
Case #22: : Accepted 00.04 sec 3644 KB
Case #23: : Accepted 00.04 sec 3600 KB
Case #24: : Accepted 00.00 sec 3148 KB
Case #25: : Accepted 00.04 sec 3520 KB
Case #26: : Accepted 00.05 sec 3436 KB
Case #27: : Accepted 00.04 sec 3456 KB
Case #28: : Accepted 00.04 sec 3644 KB
Case #29: : Accepted 00.04 sec 3504 KB
Case #30: : Accepted 00.03 sec 3300 KB
Case #31: : Accepted 00.00 sec 3488 KB
Case #32: : Accepted 00.00 sec 3160 KB
Case #33: : Accepted 00.00 sec 3124 KB
Case #34: : Accepted 00.00 sec 3160 KB
Case #35: : Accepted 00.00 sec 3080 KB
Case #36: : Accepted 00.00 sec 3040 KB
Case #37: : Accepted 00.00 sec 3100 KB
Case #38: : Accepted 00.00 sec 3040 KB
Case #39: : Accepted 00.00 sec 3112 KB
Case #40: : Accepted 00.00 sec 3116 KB
Case #41: : Accepted 00.00 sec 3120 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags