結果

問題 No.5002 stick xor
ユーザー motimoti
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0