Submission #2074610

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int L;
vector<vector<int>> fireworks;

int dp[2000][2001];

int move(int now_firework, int now_position){
    if(now_firework == fireworks.size()){
        return 0;
    }else if(dp[now_firework][now_position] != -1){
        return dp[now_firework][now_position];
    }else{
        int ans = move(now_firework + 1, now_position);
        for(int i = 0; i < fireworks[now_firework].size(); i++){
            ans += abs(fireworks[now_firework][i] - now_position);
        }
        for(int i = now_position + 1; i <= 2000; i++){
            int this_ans = move(now_firework + 1, i);
            for(int j = 0; j < fireworks[now_firework].size(); j++){
                this_ans += abs(fireworks[now_firework][j] - i);
            }
            ans = min(ans, this_ans);
        }
        return dp[now_firework][now_position] = ans;
    }
}

int main(){
    int N;
    cin >> N >> L;
    int back_time, first_firework_position;
    cin >> back_time >> first_firework_position;
    vector<int> equal_time_fireworks{first_firework_position};
    for(int i = 1; i < N; i++){
        int time, position;
        cin >> time >> position;
        if(time == back_time){
            equal_time_fireworks.push_back(position);
        }else{
            fireworks.push_back(equal_time_fireworks);
            equal_time_fireworks = {position};
            back_time = time;
        }
    }
    fireworks.push_back(equal_time_fireworks);
    for(int i = 0; i < 2000; i++){
        for(int j = 0; j <= 2000; j++){
            dp[i][j] = -1;
        }
    }
    cout << move(0, 0) << endl;
}

Submission Info

Judge Result