Submission #1142049
Source Code Expand
#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdio.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <list>
#include <utility>
#include <set>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <random>
using namespace std;
static const double EPS = 1e-9;
template<class T> bool INRANGE(T x, T a, T b) { return a <= x&&x <= b; }
template<class T> void amin(T &a, T v) { if (a > v) a = v; }
template<class T> void amax(T &a, T v) { if (a < v) a = v; }
int ROUND(double x) { return (int)(x + 0.5); }
bool ISINT(double x) { return fabs(ROUND(x) - x) <= EPS; }
bool ISEQUAL(double x, double y) { return fabs(x - y) <= EPS*max(1.0, max(fabs(x), fabs(y))); }
double SQSUM(double x, double y) { return x*x + y*y; }
#define PI (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))
#define NG (-1)
#define BIG ((int)1e9+10)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef unsigned long long ull;
typedef long long ll;
struct PIECE
{
char y[8];
char x[8];
char num;
int score;
};
int main()
{
// freopen("_google_code_jam_output.txt", "w", stdout);
int H, W, K;
scanf("%d %d %d", &H, &W, &K);
vector <string> vs;
for (int y = 0; y < H; y++)
{
string s;
cin >> s;
vs.push_back(s);
}
vector < vector <bool> > used(H, vector <bool>(W));
// ベストな1個を探す
vector <PIECE> answer;
for (double minBaseScore = 7.0; minBaseScore>=1.0; )
{
// BEGIN CUT HERE
// cout << " minBaseScore=" << minBaseScore << endl;
// END CUT HERE
// BEGIN CUT HERE
// cout << " minBaseScore=" << minBaseScore << endl;
// END CUT HERE
queue < PIECE > q;
for (int y = 0; y < H; y++)
{
for (int x = 0; x < W; x++)
{
if (!used[y][x])
{
// たぶん数字が低いところは突っ込まなくてよい。
PIECE piece;
piece.y[0] = y;
piece.x[0] = x;
piece.num = 1;
piece.score = vs[y][x] - '0';
q.push(piece);
}
}
}
int bestScore = NG;
PIECE bestPiece;
int numFinalPiece = 0;
vector <int> minScore;
for (int i = 0; i < K+1; ++i)
{
const int ms = pow(minBaseScore, i);
minScore.push_back(ms);
// cout << ms << endl;
}
while (!q.empty())
{
PIECE p = q.front();
q.pop();
// すべて1マス伸ばしてみる
for (int i = 0; i < p.num; i++)
{
const char& y = p.y[i];
const char& x = p.x[i];
// 全方向に伸ばしてみる
{
const static int dy[] = { -1, 0, 1, 0 }; // U,R,D,L
const static int dx[] = { 0, 1, 0,-1 };
for (int d = 0; d < 4; ++d)
{
const int ny = y + dy[d];
const int nx = x + dx[d];
// 範囲内
if (INRANGE(ny, 0, H - 1) && INRANGE(nx, 0, W - 1) && !used[ny][nx])
{
bool ok = true;
// ただし同じマスを含んではいけない。
for (int k = 0; k < p.num; k++)
{
if (ny == p.y[k] && nx == p.x[k])
{
ok = false;
break;
}
}
const int nextScore = p.score * (vs[ny][nx] - '0');
if (ok && nextScore >= minScore[p.num + 1])
{
PIECE nextP = p;
nextP.y[nextP.num] = ny;
nextP.x[nextP.num] = nx;
nextP.score = nextScore;
nextP.num++;
if (nextP.num == K)
{
numFinalPiece++;
if (nextP.score > bestScore)
{
bestScore = nextP.score;
bestPiece = nextP;
}
}
else
{
q.push(nextP);
}
}
}
}
}
}
}
if (bestScore != NG)
{
answer.push_back(bestPiece);
// // BEGIN CUT HERE
// cerr << " numFinalPiece=" << numFinalPiece << endl;
// // BEGIN CUT HERE
// cout << " bestScore=" << bestScore << endl;
for (int i = 0; i < K; i++)
{
const int y = bestPiece.y[i];
const int x = bestPiece.x[i];
// printf("y=%d x=%d num=%d\n", y, x, vs[y][x] - '0');
used[y][x]=true;
}
}
else
{
minBaseScore-= 0.2;
}
}
cout << SZ(answer) << endl;
for (int i=0;i<SZ(answer);++i)
{
for (int k = 0; k < K; k++)
{
printf("%d %d\n", 1+answer[i].y[k], 1+answer[i].x[k]);
}
}
// END CUT HERE
// END CUT HERE
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
shindannin |
Language |
C++14 (GCC 5.4.1) |
Score |
944802 |
Code Size |
4769 Byte |
Status |
AC |
Exec Time |
9792 ms |
Memory |
32924 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:64:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &H, &W, &K);
^
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
95706 / 1343058 |
90263 / 1343058 |
97471 / 1343058 |
90323 / 1343058 |
102192 / 1343058 |
90516 / 1343058 |
97429 / 1343058 |
86987 / 1343058 |
99087 / 1343058 |
94828 / 1343058 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
7597 ms |
27804 KB |
subtask_01_02.txt |
AC |
7216 ms |
30876 KB |
subtask_01_03.txt |
AC |
8018 ms |
32924 KB |
subtask_01_04.txt |
AC |
6173 ms |
19628 KB |
subtask_01_05.txt |
AC |
9792 ms |
27040 KB |
subtask_01_06.txt |
AC |
5096 ms |
23488 KB |
subtask_01_07.txt |
AC |
7670 ms |
25628 KB |
subtask_01_08.txt |
AC |
5995 ms |
21696 KB |
subtask_01_09.txt |
AC |
7026 ms |
24256 KB |
subtask_01_10.txt |
AC |
8203 ms |
26396 KB |