제출 #1239269

#제출 시각아이디문제언어결과실행 시간메모리
1239269sahDomino (COCI15_domino)C++20
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct Edge { int u, v; int w; }; int N, K; vector<ll> used; vector<Edge> edges; vector<ll> prefix; ll bestCover = 0; void dfs(int pos, int taken, ll curSum) { if (taken == K) { bestCover = max(bestCover, curSum); return; } int rem = K - taken; if (pos + rem > (int)edges.size()) return; // upper bound: sum of next rem weights ll ub = curSum + (prefix[pos + rem] - prefix[pos]); if (ub <= bestCover) return; // try take edges[pos] const auto &e = edges[pos]; if (!used[e.u] && !used[e.v]) { used[e.u] = used[e.v] = 1; dfs(pos + 1, taken + 1, curSum + e.w); used[e.u] = used[e.v] = 0; } // try skip dfs(pos + 1, taken, curSum); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> K; vector<vector<int>> A(N, vector<int>(N)); ll total = 0; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ cin >> A[i][j]; total += A[i][j]; } } // build edge list edges.reserve(2LL * N * (N - 1)); auto idx = [&](int i,int j){ return i * N + j; }; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if (i+1 < N) { edges.push_back({ idx(i,j), idx(i+1,j), A[i][j] + A[i+1][j] }); } if (j+1 < N) { edges.push_back({ idx(i,j), idx(i,j+1), A[i][j] + A[i][j+1] }); } } } // sort by weight descending sort(edges.begin(), edges.end(), [](auto &a, auto &b){ return a.w > b.w; }); // cap to top L edges for search const int L = min<int>(edges.size(), 2000); edges.resize(L); // prefix sums of weights prefix.assign(L+1, 0); for(int i = 0; i < L; i++){ prefix[i+1] = prefix[i] + edges[i].w; } // greedy initial solution to seed bestCover used.assign(N * N, 0); int got = 0; ll greed = 0; for(auto &e : edges){ if (got == K) break; if (!used[e.u] && !used[e.v]) { used[e.u] = used[e.v] = 1; greed += e.w; got++; } } bestCover = (got == K ? greed : 0); // clear usage for exact search fill(used.begin(), used.end(), 0); // branch‐and‐bound search dfs(0, 0, 0LL); // answer = total sum – max covered cout << (total - bestCover) << "\n";     return 0; }

컴파일 시 표준 에러 (stderr) 메시지

domino.cpp:102:1: error: extended character   is not valid in an identifier
  102 |     return 0;
      | ^
domino.cpp:102:1: error: extended character   is not valid in an identifier
domino.cpp:102:1: error: extended character   is not valid in an identifier
domino.cpp:102:1: error: extended character   is not valid in an identifier
domino.cpp:102:1: error: extended character   is not valid in an identifier
domino.cpp: In function 'int main()':
domino.cpp:102:1: error: '\U000000a0\U000000a0\U000000a0\U000000a0return\U000000a00' was not declared in this scope
  102 |     return 0;
      | ^~~~~~~~~~~~