結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-27 20:32:07 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 1,000 ms |
コード長 | 1,721 bytes |
コンパイル時間 | 2,734 ms |
実行使用メモリ | 3,684 KB |
スコア | 33,793 |
最終ジャッジ日時 | 2022-07-31 03:19:05 |
合計ジャッジ時間 | 4,096 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>#define REP(i,a,b) for(int i=a;i<b;i++)#define rep(i,n) REP(i,0,n)using namespace std;int INF = 1<<29;int a[61][61];vector<pair<int, int>> lraw;int l[666];int lsum[66][66];int N, K;void calc_xlsum(int i) {for (int j = N - 1; j >= 0; j--) {lsum[i][j] = (a[i][j] ? 1 : -1) + (j < N - 1 ? lsum[i][j + 1] : 0);}}void solve() {// int raw = 0;// rep(i, N) rep(j, N) raw += !a[i][j];vector<tuple<int, int, int, int>> vec;// int ret = raw;rep(k, K) {int mx = -INF;int idx_i = -1, idx_j = -1;rep(i, N) rep(j, N - l[k] + 1) {int cand = lsum[i][j] - ( j + l[k] < N ? lsum[i][j + l[k]] : 0 );if (mx < cand) {mx = cand;idx_i = i, idx_j = j;}}// ret += mx;vec.emplace_back(idx_i, idx_j, idx_i, idx_j + l[k] - 1);REP(j, idx_j, idx_j + l[k]) {a[idx_i][j] ^= 1;}/*printf("-------------------\n");rep(i, N) {rep(j, N) {printf("%3d", a[i][j]);}printf("\n");}printf("===================\n");*/calc_xlsum(idx_i);}int k = 0;vector<tuple<int, int, int, int>> res(K);for (auto e: vec) {res[lraw[k++].second] = e;}for (auto e: res) {int x, y, z, w; tie(x, y, z, w) = e;printf("%d %d %d %d\n", x + 1, y + 1, z + 1, w + 1);}// printf("ret = %d\n", ret);// printf("diff = %d\n", ret - raw);}int main() {cin >> N >> K;rep(i, K) {int l; cin >> l;lraw.emplace_back(l, i);}sort(lraw.rbegin(), lraw.rend());rep(i, K) l[i] = lraw[i].first;rep(i, N) {string s; cin >> s;rep(j, N) a[i][j] = s[j] - '0';}rep(i, N) {calc_xlsum(i);}solve();}