Submission #995619
Source Code Expand
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Random;
public class Main {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni();
long[] a = new long[n];
for(int i = 0;i < n;i++)a[i] = nl();
long dd = 10;
long ret = 0;
for(int d = 0;d < 18;d++, dd*=10){
Node root = null;
root = insertb(root, new Node(0L));
long all = 0;
for(int i = 0;i < n;i++)all += a[i];
if(all < dd/10){
continue;
}
for(int i = 0;i < n;i++){
for(Node x : nodes(root)){
long nv = (x.v + a[i]) % dd;
int ind = lowerBound(root, nv);
Node y = get(root, ind);
if(y != null && y.v == nv)continue;
Node py = get(root, ind-1);
if(y != null && py != null && y.v - py.v <= dd/10){
continue;
}
Node ppy = get(root, ind-2);
Node ny = get(root, ind+1);
if(ny != null && ny.v - nv <= dd/10){
root = erase(root, ind);
}
if(ppy != null && nv - ppy.v <= dd/10){
root = erase(root, ind-1);
}
root = insertb(root, new Node(nv));
}
}
Node last = get(root, count(root)-1);
ret += last.v / (dd/10);
}
out.println(ret);
}
public static Random gen = new Random();
static public class Node
{
public long v; // value
public long priority;
public Node left, right, parent;
public int count;
public Node(long v)
{
this.v = v;
priority = gen.nextLong();
update(this);
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Node [v=");
builder.append(v);
builder.append(", count=");
builder.append(count);
builder.append(", parent=");
builder.append(parent != null ? parent.v : "null");
builder.append("]");
return builder.toString();
}
}
public static Node update(Node a)
{
if(a == null)return null;
a.count = 1;
if(a.left != null)a.count += a.left.count;
if(a.right != null)a.count += a.right.count;
// TODO
return a;
}
public static void propagate(Node x)
{
for(;x != null;x = x.parent)update(x);
}
public static Node disconnect(Node a)
{
if(a == null)return null;
a.left = a.right = a.parent = null;
return update(a);
}
public static Node root(Node x)
{
if(x == null)return null;
while(x.parent != null)x = x.parent;
return x;
}
public static int count(Node a)
{
return a == null ? 0 : a.count;
}
public static void setParent(Node a, Node par)
{
if(a != null)a.parent = par;
}
public static Node merge(Node a, Node b, Node... c)
{
Node x = merge(a, b);
for(Node n : c)x = merge(x, n);
return x;
}
public static Node merge(Node a, Node b)
{
if(b == null)return a;
if(a == null)return b;
if(a.priority > b.priority){
setParent(a.right, null);
setParent(b, null);
a.right = merge(a.right, b);
setParent(a.right, a);
return update(a);
}else{
setParent(a, null);
setParent(b.left, null);
b.left = merge(a, b.left);
setParent(b.left, b);
return update(b);
}
}
public static Node[] split(Node x)
{
if(x == null)return new Node[]{null, null};
if(x.left != null)x.left.parent = null;
Node[] sp = new Node[]{x.left, x};
x.left = null;
update(x);
while(x.parent != null){
Node p = x.parent;
x.parent = null;
if(x == p.left){
p.left = sp[1];
if(sp[1] != null)sp[1].parent = p;
sp[1] = p;
}else{
p.right = sp[0];
if(sp[0] != null)sp[0].parent = p;
sp[0] = p;
}
update(p);
x = p;
}
return sp;
}
public static Node[] split(Node a, int... ks)
{
int n = ks.length;
if(n == 0)return new Node[]{a};
for(int i = 0;i < n-1;i++){
if(ks[i] > ks[i+1])throw new IllegalArgumentException(Arrays.toString(ks));
}
Node[] ns = new Node[n+1];
Node cur = a;
for(int i = n-1;i >= 0;i--){
Node[] sp = split(cur, ks[i]);
cur = sp[0];
ns[i] = sp[0];
ns[i+1] = sp[1];
}
return ns;
}
// [0,K),[K,N)
public static Node[] split(Node a, int K)
{
if(a == null)return new Node[]{null, null};
if(K <= count(a.left)){
setParent(a.left, null);
Node[] s = split(a.left, K);
a.left = s[1];
setParent(a.left, a);
s[1] = update(a);
return s;
}else{
setParent(a.right, null);
Node[] s = split(a.right, K-count(a.left)-1);
a.right = s[0];
setParent(a.right, a);
s[0] = update(a);
return s;
}
}
public static Node insertb(Node root, Node x)
{
int ind = lowerBound(root, x.v);
return insert(root, ind, x);
}
public static Node insert(Node a, int K, Node b)
{
if(a == null)return b;
if(b.priority < a.priority){
if(K <= count(a.left)){
a.left = insert(a.left, K, b);
setParent(a.left, a);
}else{
a.right = insert(a.right, K-count(a.left)-1, b);
setParent(a.right, a);
}
return update(a);
}else{
Node[] ch = split(a, K);
b.left = ch[0]; b.right = ch[1];
setParent(b.left, b);
setParent(b.right, b);
return update(b);
}
}
// delete K-th
public static Node erase(Node a, int K)
{
if(a == null)return null;
if(K < count(a.left)){
a.left = erase(a.left, K);
setParent(a.left, a);
return update(a);
}else if(K == count(a.left)){
setParent(a.left, null);
setParent(a.right, null);
Node aa = merge(a.left, a.right);
disconnect(a);
return aa;
}else{
a.right = erase(a.right, K-count(a.left)-1);
setParent(a.right, a);
return update(a);
}
}
public static Node get(Node a, int K)
{
if(K < 0)return null;
if(K >= count(a))return null;
while(a != null){
if(K < count(a.left)){
a = a.left;
}else if(K == count(a.left)){
break;
}else{
K = K - count(a.left)-1;
a = a.right;
}
}
return a;
}
public static int index(Node a)
{
if(a == null)return -1;
int ind = count(a.left);
while(a != null){
Node par = a.parent;
if(par != null && par.right == a){
ind += count(par.left) + 1;
}
a = par;
}
return ind;
}
public static Node mergeTechnically(Node x, Node y)
{
if(count(x) > count(y)){
Node d = x; x = y; y = d;
}
// |x|<=|y|
for(Node cur : nodesdfs(x))y = insertb(y, disconnect(cur));
return y;
}
public static int lowerBound(Node a, long q)
{
int lcount = 0;
while(a != null){
if(a.v >= q){
a = a.left;
}else{
lcount += count(a.left) + 1;
a = a.right;
}
}
return lcount;
}
public static int search(Node a, int q)
{
int lcount = 0;
while(a != null){
if(a.v == q){
lcount += count(a.left);
break;
}
if(q < a.v){
a = a.left;
}else{
lcount += count(a.left) + 1;
a = a.right;
}
}
return a == null ? -(lcount+1) : lcount;
}
public static Node next(Node x)
{
if(x == null)return null;
if(x.right != null){
x = x.right;
while(x.left != null)x = x.left;
return x;
}else{
while(true){
Node p = x.parent;
if(p == null)return null;
if(p.left == x)return p;
x = p;
}
}
}
public static Node prev(Node x)
{
if(x == null)return null;
if(x.left != null){
x = x.left;
while(x.right != null)x = x.right;
return x;
}else{
while(true){
Node p = x.parent;
if(p == null)return null;
if(p.right == x)return p;
x = p;
}
}
}
public static Node[] nodes(Node a) { return nodes(a, new Node[count(a)], 0, count(a)); }
public static Node[] nodes(Node a, Node[] ns, int L, int R)
{
if(a == null)return ns;
nodes(a.left, ns, L, L+count(a.left));
ns[L+count(a.left)] = a;
nodes(a.right, ns, R-count(a.right), R);
return ns;
}
// faster than nodes but inconsistent
public static Node[] nodesdfs(Node a) { return nodesdfs(a, new Node[a.count], new int[]{0}); }
public static Node[] nodesdfs(Node a, Node[] ns, int[] pos)
{
if(a == null)return ns;
ns[pos[0]++] = a;
nodesdfs(a.left, ns, pos);
nodesdfs(a.right, ns, pos);
return ns;
}
public static String toString(Node a, String indent)
{
if(a == null)return "";
StringBuilder sb = new StringBuilder();
sb.append(toString(a.left, indent + " "));
sb.append(indent).append(a).append("\n");
sb.append(toString(a.right, indent + " "));
return sb.toString();
}
public static void main(String[] args) throws Exception
{
// int n = 20000, m = 99999;
// Random gen = new Random();
// StringBuilder sb = new StringBuilder();
// sb.append(n + " ");
// for (int i = 0; i < n; i++) {
// sb.append(gen.nextInt(1000000000) + " ");
// }
// INPUT = sb.toString();
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
// private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Submission Info
Submission Time |
|
Task |
B - Exact Payment |
User |
uwi |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
1500 |
Code Size |
12084 Byte |
Status |
AC |
Exec Time |
535 ms |
Memory |
31076 KB |
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
1500 / 1500 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
All |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 01-47.txt, 01-48.txt, 01-49.txt, 01-50.txt, 01-51.txt, 01-52.txt, 01-53.txt, 01-54.txt, 01-55.txt, 01-56.txt, 01-57.txt, 01-58.txt, 01-59.txt, 01-60.txt, 01-61.txt, 01-62.txt, 01-63.txt, 01-64.txt, 01-65.txt, 01-66.txt, 01-67.txt, 01-68.txt, 01-69.txt, 01-70.txt, 01-71.txt, 01-72.txt, 01-73.txt, 01-74.txt, 01-75.txt, 01-76.txt, 01-77.txt, 01-78.txt, 01-79.txt, 01-80.txt, 01-81.txt, 01-82.txt, 01-83.txt, 01-84.txt, 01-85.txt, 01-86.txt, 01-87.txt, 01-88.txt, 01-89.txt, 01-90.txt, 01-91.txt, 01-92.txt, 01-93.txt, 01-94.txt, 01-95.txt, 01-96.txt, 01-97.txt, 01-98.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
98 ms |
8144 KB |
01-02.txt |
AC |
103 ms |
8276 KB |
01-03.txt |
AC |
97 ms |
8272 KB |
01-04.txt |
AC |
98 ms |
8272 KB |
01-05.txt |
AC |
99 ms |
8404 KB |
01-06.txt |
AC |
452 ms |
26660 KB |
01-07.txt |
AC |
445 ms |
26656 KB |
01-08.txt |
AC |
424 ms |
26960 KB |
01-09.txt |
AC |
487 ms |
27012 KB |
01-10.txt |
AC |
384 ms |
26800 KB |
01-11.txt |
AC |
418 ms |
26880 KB |
01-12.txt |
AC |
424 ms |
27972 KB |
01-13.txt |
AC |
458 ms |
26780 KB |
01-14.txt |
AC |
485 ms |
28236 KB |
01-15.txt |
AC |
438 ms |
26700 KB |
01-16.txt |
AC |
436 ms |
26536 KB |
01-17.txt |
AC |
512 ms |
28280 KB |
01-18.txt |
AC |
481 ms |
28216 KB |
01-19.txt |
AC |
455 ms |
28048 KB |
01-20.txt |
AC |
444 ms |
26588 KB |
01-21.txt |
AC |
460 ms |
26964 KB |
01-22.txt |
AC |
498 ms |
28548 KB |
01-23.txt |
AC |
477 ms |
27240 KB |
01-24.txt |
AC |
411 ms |
26860 KB |
01-25.txt |
AC |
444 ms |
28180 KB |
01-26.txt |
AC |
503 ms |
28440 KB |
01-27.txt |
AC |
493 ms |
28356 KB |
01-28.txt |
AC |
415 ms |
26644 KB |
01-29.txt |
AC |
438 ms |
26508 KB |
01-30.txt |
AC |
477 ms |
27160 KB |
01-31.txt |
AC |
473 ms |
28416 KB |
01-32.txt |
AC |
429 ms |
27020 KB |
01-33.txt |
AC |
431 ms |
28096 KB |
01-34.txt |
AC |
467 ms |
27120 KB |
01-35.txt |
AC |
501 ms |
28612 KB |
01-36.txt |
AC |
403 ms |
26416 KB |
01-37.txt |
AC |
446 ms |
28096 KB |
01-38.txt |
AC |
487 ms |
28624 KB |
01-39.txt |
AC |
477 ms |
26656 KB |
01-40.txt |
AC |
500 ms |
28352 KB |
01-41.txt |
AC |
443 ms |
27052 KB |
01-42.txt |
AC |
484 ms |
28400 KB |
01-43.txt |
AC |
491 ms |
28652 KB |
01-44.txt |
AC |
449 ms |
26628 KB |
01-45.txt |
AC |
507 ms |
28208 KB |
01-46.txt |
AC |
482 ms |
28508 KB |
01-47.txt |
AC |
451 ms |
27084 KB |
01-48.txt |
AC |
465 ms |
28612 KB |
01-49.txt |
AC |
447 ms |
28128 KB |
01-50.txt |
AC |
439 ms |
28188 KB |
01-51.txt |
AC |
448 ms |
28268 KB |
01-52.txt |
AC |
499 ms |
28620 KB |
01-53.txt |
AC |
486 ms |
28592 KB |
01-54.txt |
AC |
484 ms |
28512 KB |
01-55.txt |
AC |
434 ms |
28032 KB |
01-56.txt |
AC |
443 ms |
28248 KB |
01-57.txt |
AC |
432 ms |
28236 KB |
01-58.txt |
AC |
476 ms |
28052 KB |
01-59.txt |
AC |
479 ms |
28152 KB |
01-60.txt |
AC |
473 ms |
28132 KB |
01-61.txt |
AC |
491 ms |
28172 KB |
01-62.txt |
AC |
444 ms |
28040 KB |
01-63.txt |
AC |
458 ms |
28180 KB |
01-64.txt |
AC |
452 ms |
28048 KB |
01-65.txt |
AC |
481 ms |
28308 KB |
01-66.txt |
AC |
262 ms |
23904 KB |
01-67.txt |
AC |
449 ms |
28372 KB |
01-68.txt |
AC |
518 ms |
30896 KB |
01-69.txt |
AC |
511 ms |
28688 KB |
01-70.txt |
AC |
446 ms |
28480 KB |
01-71.txt |
AC |
285 ms |
25272 KB |
01-72.txt |
AC |
304 ms |
24748 KB |
01-73.txt |
AC |
286 ms |
26188 KB |
01-74.txt |
AC |
276 ms |
26544 KB |
01-75.txt |
AC |
237 ms |
23776 KB |
01-76.txt |
AC |
283 ms |
26532 KB |
01-77.txt |
AC |
535 ms |
31076 KB |
01-78.txt |
AC |
282 ms |
26304 KB |
01-79.txt |
AC |
299 ms |
26808 KB |
01-80.txt |
AC |
289 ms |
26444 KB |
01-81.txt |
AC |
280 ms |
26508 KB |
01-82.txt |
AC |
294 ms |
26192 KB |
01-83.txt |
AC |
280 ms |
26100 KB |
01-84.txt |
AC |
265 ms |
25760 KB |
01-85.txt |
AC |
300 ms |
26352 KB |
01-86.txt |
AC |
301 ms |
25204 KB |
01-87.txt |
AC |
254 ms |
24664 KB |
01-88.txt |
AC |
285 ms |
27048 KB |
01-89.txt |
AC |
308 ms |
25184 KB |
01-90.txt |
AC |
529 ms |
29088 KB |
01-91.txt |
AC |
295 ms |
26708 KB |
01-92.txt |
AC |
288 ms |
25544 KB |
01-93.txt |
AC |
274 ms |
26216 KB |
01-94.txt |
AC |
297 ms |
26604 KB |
01-95.txt |
AC |
329 ms |
27532 KB |
01-96.txt |
AC |
509 ms |
28800 KB |
01-97.txt |
AC |
290 ms |
26416 KB |
01-98.txt |
AC |
298 ms |
26824 KB |
sample-01.txt |
AC |
97 ms |
8144 KB |
sample-02.txt |
AC |
102 ms |
8400 KB |