Submission #1175844


Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;
const int INFTY = 1000000;

int W, H, Q;
int T[100000], D[100000], X[100000];

int w[2];
vector<int> v[2][100001];
int dp[100000];
int tmax = 100000;

int main() {

    // input
    cin >> W >> H >> Q;
    rep(i, Q){
        cin >> T[i] >> D[i] >> X[i];
        X[i]--; // 0 - W-1/H-1
    }

    rep(i, Q){
        v[D[i]][T[i]].push_back(X[i]);
    }
    w[0] = W; // vertical beam
    w[1] = H; // horizontal beam

    int ret[2];
    ret[0] = INFTY;
    ret[1] = INFTY;

    // run
    rep(k, 2){

        rep(j, w[k]){
            dp[j] = 0;
        }

        for(int t = 1; t<=tmax; t++){

            // update ex-beam cell
            for(int& q: v[k][t-1]){
                int temp;

                temp = q-1;
                while(temp >= 0){
                    if(dp[temp] != INFTY){
                        dp[q] = min(dp[q], dp[temp] + abs(q - temp));
                        break;
                    }
                    temp--;
                }

                temp = q+1;
                while(temp < w[k]){
                    if(dp[temp] != INFTY){
                        dp[q] = min(dp[q], dp[temp] + abs(q - temp));
                        break;
                    }
                    temp++;
                }

            }

            // beam
            for(int& q: v[k][t]){
                dp[q] = INFTY;
            }
        }

        rep(j, w[k]){
            ret[k] = min(ret[k], dp[j]);
        }

    }

    if(ret[0] == INFTY || ret[1] == INFTY){
        cout << -1 << endl;
    }
    else{
        cout << ret[0] + ret[1] << endl;
    }
}

Submission Info

Submission Time
Task C - ビーム
User threecourse
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2181 Byte
Status AC
Exec Time 101 ms
Memory 9216 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 3
AC × 33
AC × 63
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt
Case Name Status Exec Time Memory
sample_01.txt AC 3 ms 6016 KB
sample_02.txt AC 3 ms 6016 KB
sample_03.txt AC 3 ms 6016 KB
subtask1_01.txt AC 3 ms 6016 KB
subtask1_02.txt AC 3 ms 6016 KB
subtask1_03.txt AC 3 ms 6016 KB
subtask1_04.txt AC 3 ms 6016 KB
subtask1_05.txt AC 3 ms 6016 KB
subtask1_06.txt AC 3 ms 6016 KB
subtask1_07.txt AC 3 ms 6016 KB
subtask1_08.txt AC 3 ms 6016 KB
subtask1_09.txt AC 3 ms 6016 KB
subtask1_10.txt AC 3 ms 6016 KB
subtask1_11.txt AC 3 ms 6016 KB
subtask1_12.txt AC 3 ms 6016 KB
subtask1_13.txt AC 3 ms 6016 KB
subtask1_14.txt AC 3 ms 6016 KB
subtask1_15.txt AC 3 ms 6016 KB
subtask1_16.txt AC 3 ms 6016 KB
subtask1_17.txt AC 3 ms 6016 KB
subtask1_18.txt AC 3 ms 6016 KB
subtask1_19.txt AC 3 ms 6016 KB
subtask1_20.txt AC 3 ms 6016 KB
subtask1_21.txt AC 3 ms 6016 KB
subtask1_22.txt AC 3 ms 6016 KB
subtask1_23.txt AC 3 ms 6016 KB
subtask1_24.txt AC 3 ms 6016 KB
subtask1_25.txt AC 3 ms 6016 KB
subtask1_26.txt AC 3 ms 6016 KB
subtask1_27.txt AC 3 ms 6016 KB
subtask1_28.txt AC 3 ms 6016 KB
subtask1_29.txt AC 3 ms 6016 KB
subtask1_30.txt AC 3 ms 6016 KB
subtask2_01.txt AC 91 ms 8576 KB
subtask2_02.txt AC 94 ms 8576 KB
subtask2_03.txt AC 83 ms 9216 KB
subtask2_04.txt AC 74 ms 6656 KB
subtask2_05.txt AC 75 ms 6784 KB
subtask2_06.txt AC 101 ms 8960 KB
subtask2_07.txt AC 89 ms 8576 KB
subtask2_08.txt AC 72 ms 6784 KB
subtask2_09.txt AC 71 ms 6784 KB
subtask2_10.txt AC 71 ms 6912 KB
subtask2_11.txt AC 75 ms 7168 KB
subtask2_12.txt AC 73 ms 6656 KB
subtask2_13.txt AC 83 ms 8704 KB
subtask2_14.txt AC 91 ms 8576 KB
subtask2_15.txt AC 5 ms 6016 KB
subtask2_16.txt AC 3 ms 6016 KB
subtask2_17.txt AC 74 ms 6656 KB
subtask2_18.txt AC 94 ms 9216 KB
subtask2_19.txt AC 101 ms 8448 KB
subtask2_20.txt AC 73 ms 6912 KB
subtask2_21.txt AC 79 ms 7680 KB
subtask2_22.txt AC 78 ms 7424 KB
subtask2_23.txt AC 82 ms 9216 KB
subtask2_24.txt AC 75 ms 6912 KB
subtask2_25.txt AC 79 ms 6784 KB
subtask2_26.txt AC 71 ms 6656 KB
subtask2_27.txt AC 73 ms 6528 KB
subtask2_28.txt AC 72 ms 6528 KB
subtask2_29.txt AC 71 ms 6784 KB
subtask2_30.txt AC 76 ms 7296 KB