Submission #3692703


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

const int T = 1000, N = 10, M = 30000;
int A[M+1], B[M+1], S[M+1][N+1];
int64_t C[M+1];
bitset<M+1> used;

vector<int> end2i[T+1];

int skillLevel[N+1];
int skillPoint[N+1];
int64_t mymoney = 0;
bool skill_max = false;

const int MAX_SKILL = 10;
bool try_skillup(){
    int i = 1;
    for(int i2=2; i2<=N; i2++) if(skillLevel[i] > skillLevel[i2]) i = i2;
    if(skillLevel[i] >= MAX_SKILL) return false;
    int64_t money = 10000LL * (1<<(skillLevel[i]+1));
    if(mymoney >= money){
        cout << "1 " << i << endl;
        mymoney -= money;
        skillPoint[i]++;
        if(skillPoint[i] == skillLevel[i]+1){
            skillLevel[i]++;
            skillPoint[i] = 0;
            if(i == N && skillLevel[i] == MAX_SKILL) skill_max = true;
        }
        return true;
    }else{
        return false;
    }
}

int64_t payment(int i, int t){
    if(t < A[i] || t > B[i]) return 0;
    double AddMoney = C[i];
    AddMoney *= (1 + 9 * (double)(t - A[i]) / (B[i] - A[i]));
    int SkillLack = 0;
    for (int j = 1; j <= N; j++) SkillLack += max(0, S[i][j] - skillLevel[j]);

    if (SkillLack == 0) AddMoney *= 10;
    else {
        AddMoney *= pow(0.5, SkillLack);
        AddMoney += 1e-9;
    }
    return (int64_t) AddMoney;
}

int find_better_job(int t){
    int mxi = -1;
    int64_t mx = 1000;
    for(int t2=t; t2<=T; t2++){
        for(int i : end2i[t2]){
            if(used[i]) continue;
            int64_t result = payment(i, t);
            if(mx <= result){
                mxi = i;
                mx = result;
            }
        }
    }
    used[mxi] = true;
    mymoney += mx;
    return mxi;
}

void do_job(int t){
    int mxi = -1;
    int64_t mx = 1000;
    for(int t2=t; t2<=min(T, t+20); t2++){
        for(int i : end2i[t2]){
            if(used[i]) continue;
            int64_t result = payment(i, t);
            if(mx <= result){
                mxi = i;
                mx = result;
            }
        }
    }
    if(mxi == -1){
        cout << 3 << endl;
    }else{
        cout << "2 " << mxi << endl;
        used[mxi] = true;
    }
    mymoney += mx;
}

int main(){
    int _;
    cin >> _ >> _ >> _;
    for(int i=1; i<=M; i++){
        cin >> A[i] >> B[i] >> C[i];
        for(int j=1; j<=N; j++) cin >> S[i][j];
        end2i[B[i]].push_back(i);
    }

    int t2 = T+1;
    for(int t=1; t<=T; t++){
        if(skill_max){
            cerr << "turn " << t << "  skilllevel max" << endl;
            t2 = t;
            break;
        }
        if(!try_skillup()) do_job(t);
    }

    int ans[T+1];
    for(int t=T; t>=t2; t--){
        ans[t] = find_better_job(t);
    }

    for(int t=t2; t<=T; t++){
        if(ans[t] == -1){
            cout << 3 << endl;
        }else{
            cout << "2 " << ans[t] << endl;
        }
    }

    cerr << "skill:" << endl;
    for(int i=1; i<=N; i++){
        cerr << i << " " << skillLevel[i] << endl;
    }
    cerr << "money: "<< mymoney << endl;
    return 0;
}

Submission Info

Submission Time
Task A - モンスターテイマー
User betrue12
Language C++14 (GCC 5.4.1)
Score 319377481.54
Code Size 3135 Byte
Status
Exec Time 169 ms
Memory 2304 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 1382375.76 / 1000 example_01.txt
All 317995105.78 / 30000 example_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_01_27.txt, subtask_01_28.txt, subtask_01_29.txt, subtask_01_30.txt
Case Name Status Exec Time Memory
example_01.txt 164 ms 2304 KB
subtask_01_02.txt 163 ms 2304 KB
subtask_01_03.txt 164 ms 2304 KB
subtask_01_04.txt 166 ms 2304 KB
subtask_01_05.txt 163 ms 2304 KB
subtask_01_06.txt 163 ms 2304 KB
subtask_01_07.txt 163 ms 2304 KB
subtask_01_08.txt 163 ms 2304 KB
subtask_01_09.txt 166 ms 2304 KB
subtask_01_10.txt 162 ms 2304 KB
subtask_01_11.txt 162 ms 2304 KB
subtask_01_12.txt 165 ms 2304 KB
subtask_01_13.txt 166 ms 2304 KB
subtask_01_14.txt 167 ms 2304 KB
subtask_01_15.txt 166 ms 2304 KB
subtask_01_16.txt 160 ms 2304 KB
subtask_01_17.txt 165 ms 2304 KB
subtask_01_18.txt 166 ms 2304 KB
subtask_01_19.txt 164 ms 2304 KB
subtask_01_20.txt 166 ms 2304 KB
subtask_01_21.txt 169 ms 2304 KB
subtask_01_22.txt 166 ms 2304 KB
subtask_01_23.txt 167 ms 2304 KB
subtask_01_24.txt 168 ms 2304 KB
subtask_01_25.txt 168 ms 2304 KB
subtask_01_26.txt 163 ms 2304 KB
subtask_01_27.txt 168 ms 2304 KB
subtask_01_28.txt 167 ms 2304 KB
subtask_01_29.txt 165 ms 2304 KB
subtask_01_30.txt 163 ms 2304 KB