Submission #2120508
Source Code Expand
#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <queue> #include <set> #include <map> #include <cmath> #include <iomanip> #include <cassert> #include <bitset> using namespace std; typedef pair<int, int> P; #define rep(i, n) for (int i=0; i<(n); i++) #define all(c) (c).begin(), (c).end() #define uniq(c) c.erase(unique(all(c)), (c).end()) #define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin()) #define _1 first #define _2 second #define pb push_back #define INF 1145141919 #define MOD 1000000007 #define MAX_V 301 struct Dinic { struct Edge { int to, cap, rev; }; vector<Edge> G[MAX_V]; int level[MAX_V], iter[MAX_V]; void add_edge(int x, int y, int cap) { G[x].pb((Edge) { y, cap, (int)G[y].size() }); G[y].pb((Edge) { x, 0, (int)G[x].size()-1 }); } void bfs(int s) { rep(i, MAX_V) level[i] = INF; queue<int> q; q.push(s); level[s] = 0; while (!q.empty()) { int x = q.front(); q.pop(); for (Edge e : G[x]) if (e.cap > 0 && level[e.to] == INF) { level[e.to] = level[x]+1; q.push(e.to); } } } int dfs(int x, int goal, int f) { if (x == goal) return f; for (int &i=iter[x]; i<G[x].size(); i++) { Edge &e = G[x][i]; if (e.cap > 0 && level[x] < level[e.to]) { int w = dfs(e.to, goal, min(f, e.cap)); if (w > 0) { e.cap -= w; G[e.to][e.rev].cap += w; return w; } } } return 0; } int max_flow(int s, int t) { int flow = 0; while (true) { bfs(s); if (level[t] == INF) return flow; rep(i, MAX_V) iter[i] = 0; while (true) { int f = dfs(s, t, INF); if (f == 0) break; flow += f; } } } }; int Q; int A[301]; Dinic dinic; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> Q; rep(i, Q) { int m, x; cin >> m >> x; A[m] += x; } for (int x=2; x<=300; x++) { for (int t=2; t<x; t++) if (x%t == 0) { dinic.add_edge(x, t, INF); } } int S = 0, T = 1; int sum = 0; for (int i=2; i<=300; i++) { int x = A[i]; if (x == 0) continue; if (x > 0) { sum += x; dinic.add_edge(S, i, x); } else { dinic.add_edge(i, T, -x); } } cout << sum - dinic.max_flow(S, T) << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - Akashic Records |
User | funcsr |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2499 Byte |
Status | WA |
Exec Time | 2 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03 |
All | a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55, b56, b57, b58, b59, b60, b61, b62, b63 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 1 ms | 256 KB |
a02 | AC | 1 ms | 256 KB |
a03 | AC | 1 ms | 256 KB |
b04 | AC | 1 ms | 256 KB |
b05 | AC | 2 ms | 384 KB |
b06 | AC | 2 ms | 384 KB |
b07 | WA | 1 ms | 256 KB |
b08 | WA | 2 ms | 384 KB |
b09 | AC | 1 ms | 256 KB |
b10 | WA | 1 ms | 256 KB |
b11 | WA | 2 ms | 256 KB |
b12 | WA | 2 ms | 256 KB |
b13 | WA | 2 ms | 384 KB |
b14 | WA | 2 ms | 384 KB |
b15 | WA | 2 ms | 384 KB |
b16 | WA | 2 ms | 384 KB |
b17 | WA | 2 ms | 384 KB |
b18 | WA | 2 ms | 384 KB |
b19 | WA | 2 ms | 384 KB |
b20 | WA | 2 ms | 384 KB |
b21 | WA | 2 ms | 384 KB |
b22 | WA | 2 ms | 384 KB |
b23 | WA | 2 ms | 384 KB |
b24 | WA | 2 ms | 384 KB |
b25 | WA | 2 ms | 384 KB |
b26 | WA | 2 ms | 384 KB |
b27 | WA | 2 ms | 384 KB |
b28 | WA | 2 ms | 384 KB |
b29 | WA | 2 ms | 384 KB |
b30 | WA | 2 ms | 384 KB |
b31 | WA | 2 ms | 384 KB |
b32 | WA | 2 ms | 384 KB |
b33 | WA | 2 ms | 384 KB |
b34 | WA | 2 ms | 384 KB |
b35 | WA | 2 ms | 384 KB |
b36 | WA | 2 ms | 384 KB |
b37 | WA | 2 ms | 384 KB |
b38 | WA | 2 ms | 384 KB |
b39 | WA | 2 ms | 384 KB |
b40 | WA | 2 ms | 384 KB |
b41 | WA | 2 ms | 384 KB |
b42 | WA | 2 ms | 384 KB |
b43 | WA | 2 ms | 384 KB |
b44 | WA | 2 ms | 384 KB |
b45 | WA | 2 ms | 384 KB |
b46 | WA | 2 ms | 384 KB |
b47 | WA | 2 ms | 384 KB |
b48 | WA | 2 ms | 384 KB |
b49 | WA | 2 ms | 384 KB |
b50 | WA | 2 ms | 384 KB |
b51 | WA | 2 ms | 384 KB |
b52 | WA | 2 ms | 384 KB |
b53 | WA | 2 ms | 384 KB |
b54 | WA | 2 ms | 384 KB |
b55 | WA | 2 ms | 384 KB |
b56 | WA | 2 ms | 384 KB |
b57 | WA | 2 ms | 384 KB |
b58 | WA | 2 ms | 384 KB |
b59 | WA | 2 ms | 384 KB |
b60 | WA | 2 ms | 384 KB |
b61 | WA | 2 ms | 384 KB |
b62 | WA | 2 ms | 384 KB |
b63 | WA | 2 ms | 384 KB |