AtCoder Regular Contest 044

Submission #1088028

Source codeソースコード

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) //cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size(); s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  s << "\n"; return s;
}

// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) { s << vv[i]; }
  return s;
}

#define INF INT_MAX/2
int tmax = 1e5;

int main() {
  vi wh(2);
  int q;
  scanf("%d %d %d", &wh[0], &wh[1], &q);
  vv<vi> beam;
  beam.resize(2);
  beam[0].reserve(q);
  beam[1].reserve(q);
  rep (i, q) {
    int t, d, x;
    scanf("%d %d %d", &t, &d, &x);
    t -= 1; x -= 1;
    beam[d].push_back({t, x});
  }

  vector<set<int> > all_wh(2);
  rep (i, 2) {
    sort(all(beam[i]));
    rep (j, wh[i]) {
      all_wh[i].insert(j);
    }
  }
  vi dp;
  vi min_dwh(2, INF);
  rep (i, 2) {
    dp.assign(wh[i], 0);
    auto itr_b = lower_bound(all(beam[i]), (vi){0, 0});
    auto itr_e = itr_b;
    rep (t, tmax) {
      itr_b = itr_e;
      itr_e = lower_bound(all(beam[i]), (vi){t+1, 0});
      if (itr_e - itr_b == wh[i]) {
        printf("-1\n");
        return 0;
      } else if (itr_b == itr_e) {
        continue;
      }
      for (auto itr = itr_e - 1; itr >= itr_b; --itr) {
        debug((*itr)[1]);
        all_wh[i].erase((*itr)[1]);
        dp[(*itr)[1]] = INF;
      }
      if (t == tmax-1) {
        break;
      }
      for (auto itr = itr_b; itr < itr_e; ++itr) {
        int target = (*itr)[1];
        int ret = INF;
        int prev_num, next_num;
        auto adj_itr = all_wh[i].lower_bound(target);
        if (adj_itr != end(all_wh[i])) {
          next_num = *(adj_itr);
          ret = min(ret, dp[next_num] + next_num - target);
        }
        if (adj_itr != begin(all_wh[i])) {
          --adj_itr;
          prev_num = *(adj_itr);
          ret = min(ret, dp[prev_num] + target - prev_num);
        }
        assert(ret < INF);
        dp[target] = ret;
        all_wh[i].insert(target);
      }
      debug(dp);
    }
    rep (j, wh[i]) {
      min_dwh[i] = min(min_dwh[i], dp[j]);
    }
  }
  printf("%d\n", min_dwh[0] + min_dwh[1]);

  return 0;
}

Submission

Task問題 C - ビーム
User nameユーザ名 cyglef
Created time投稿日時
Language言語 C++14 (Clang++ 3.4)
Status状態 AC
Score得点 100
Source lengthソースコード長 3206 Byte
File nameファイル名
Exec time実行時間 199 ms
Memory usageメモリ使用量 15988 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
Subtask1 30 / 30 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 70 / 70 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 27 ms 800 KB
sample_02.txt AC 24 ms 924 KB
sample_03.txt AC 18 ms 912 KB
subtask1_01.txt AC 25 ms 928 KB
subtask1_02.txt AC 21 ms 924 KB
subtask1_03.txt AC 25 ms 800 KB
subtask1_04.txt AC 17 ms 924 KB
subtask1_05.txt AC 25 ms 800 KB
subtask1_06.txt AC 27 ms 924 KB
subtask1_07.txt AC 26 ms 928 KB
subtask1_08.txt AC 27 ms 928 KB
subtask1_09.txt AC 27 ms 796 KB
subtask1_10.txt AC 26 ms 796 KB
subtask1_11.txt AC 25 ms 928 KB
subtask1_12.txt AC 24 ms 928 KB
subtask1_13.txt AC 16 ms 800 KB
subtask1_14.txt AC 16 ms 924 KB
subtask1_15.txt AC 23 ms 796 KB
subtask1_16.txt AC 26 ms 796 KB
subtask1_17.txt AC 27 ms 928 KB
subtask1_18.txt AC 18 ms 920 KB
subtask1_19.txt AC 25 ms 800 KB
subtask1_20.txt AC 25 ms 928 KB
subtask1_21.txt AC 24 ms 796 KB
subtask1_22.txt AC 27 ms 800 KB
subtask1_23.txt AC 27 ms 924 KB
subtask1_24.txt AC 24 ms 928 KB
subtask1_25.txt AC 23 ms 928 KB
subtask1_26.txt AC 21 ms 928 KB
subtask1_27.txt AC 27 ms 796 KB
subtask1_28.txt AC 23 ms 844 KB
subtask1_29.txt AC 25 ms 800 KB
subtask1_30.txt AC 24 ms 800 KB
subtask2_01.txt AC 110 ms 6304 KB
subtask2_02.txt AC 110 ms 6260 KB
subtask2_03.txt AC 90 ms 6252 KB
subtask2_04.txt AC 105 ms 6816 KB
subtask2_05.txt AC 120 ms 8608 KB
subtask2_06.txt AC 199 ms 15988 KB
subtask2_07.txt AC 105 ms 6252 KB
subtask2_08.txt AC 95 ms 6252 KB
subtask2_09.txt AC 95 ms 6264 KB
subtask2_10.txt AC 109 ms 7148 KB
subtask2_11.txt AC 96 ms 10860 KB
subtask2_12.txt AC 104 ms 6260 KB
subtask2_13.txt AC 93 ms 6168 KB
subtask2_14.txt AC 110 ms 6684 KB
subtask2_15.txt AC 29 ms 1048 KB
subtask2_16.txt AC 23 ms 800 KB
subtask2_17.txt AC 102 ms 6296 KB
subtask2_18.txt AC 149 ms 11352 KB
subtask2_19.txt AC 168 ms 11300 KB
subtask2_20.txt AC 101 ms 6304 KB
subtask2_21.txt AC 86 ms 6176 KB
subtask2_22.txt AC 86 ms 6180 KB
subtask2_23.txt AC 88 ms 6256 KB
subtask2_24.txt AC 86 ms 6180 KB
subtask2_25.txt AC 100 ms 6180 KB
subtask2_26.txt AC 101 ms 6308 KB
subtask2_27.txt AC 91 ms 6176 KB
subtask2_28.txt AC 92 ms 6308 KB
subtask2_29.txt AC 104 ms 7148 KB
subtask2_30.txt AC 86 ms 6176 KB