| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 735095 | SchoolAccount | Split the sequence (APIO14_sequence) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class sequence {
// change to ur file
private static final String localTestInputFile = "C:\\Users\\anaba\\eclipse-workspace\\test\\src\\main\\java\\input.in";
private static final String localTestOutputFile = "C:\\Users\\anaba\\eclipse-workspace\\test\\src\\main\\java\\input.out";
// for usaco only
private static final String name = "cowjog";
// constants to use
private static final int mod = 1_000_000_007, mm = 998244353, inf = Integer.MAX_VALUE;
private static final int[][] d4 = new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
private static final long inf2 = Long.MAX_VALUE;
// all are primes
private static final long mod1 = 4611686018427387847L, mod2 = 4611686018427387833L, mod3 = 4611686018427387813L;
// need to generate Mod.fast(int max) first to use
private static long[] fact;
private static PrintWriter out;
private static FastIO sc;
private static long time = -1;
public static void main(String[] args) throws Exception {
// super giga brain reader that accounts for all platforms and displays time when its ur own platform
try {
if(name.length() != 0 && new File(name+".in").exists()) {
sc = new FastIO(name+".in");
out = new PrintWriter(name+".out");
}else if(new File(localTestInputFile).exists()){
sc = new FastIO(localTestInputFile);
out = new PrintWriter(new BufferedOutputStream(System.out));
time = System.currentTimeMillis();
}else {
sc = new FastIO(System.in);
out = new PrintWriter(new BufferedOutputStream(System.out));
}
}catch(SecurityException e) {
sc = new FastIO(System.in);
out = new PrintWriter(new BufferedOutputStream(System.out));
}
// for(int T = sc.nextInt(); T>0; T--)
solve();
if(time != -1) System.out.println("Time: "+(System.currentTimeMillis()-time)+"ms");
out.close();
}
private static void solve() throws Exception {
int N = sc.nextInt(), K = sc.nextInt()+1;
long[] nums = sc.longArr(N);
for(int i = 1; i<N; i++) nums[i]+=nums[i-1];
long[][] dp = new long[N][K];
int[][] best = new int[N][K];
CHT<Integer>[] max = new CHT[K];
for(int i = 0; i<K; i++) max[i] = new CHT(true);
max[0].add(0, 0, -1);
for(int i = 0; i<N; i++){
for(int j = 0; j<K; j++){
Two<Long, Integer> get = max[j].get(nums[i]);
dp[i][j] = get.a;
best[i][j] = get.b;
if(j != K-1) max[j+1].add(nums[i], dp[i][j]-nums[i]*nums[i], i);
}
}
out.println(dp[N-1][K-1]);
int[] order = new int[K-1];
int c = best[N-1][K-1];
for(int i = 0; i<K-1; i++){
order[K-i-2] = c+1;
c = best[c][K-i-2];
}
out(order);
}
// Mo's algorithm
private static class MoAlg<T, Edit> {
public interface Add<Edit, T> {public void add(Edit a, T curr, boolean first);}
public interface Rem<Edit, T> {public void rem(Edit a, T curr, boolean first);}
public interface Get<Edit> {public Object get(Edit a);}
private final T[] nums;
private final int block;
private final List<int[]> quer;
private final Add<Edit, T> add;
private final Rem<Edit, T> rem;
private final Get<Edit> get;
private Edit def;
public MoAlg(T[] nums, Add<Edit, T> add, Rem<Edit, T> rem, Get<Edit> get, Edit def) {
this.add = add;
this.rem = rem;
this.get = get;
this.nums = nums;
this.def = def;
block = (int)Math.sqrt(nums.length);
quer = new ArrayList<>();
}
public void add(int l, int r) {
quer.add(new int[] {l, r, quer.size()});
}
public Object[] getAns() {
Collections.sort(quer, (a, b) -> a[0]/block == b[0]/block ? ((((a[0]/block)&1) == 0) ? a[1]-b[1]:b[1]-a[1]):a[0]-b[0]);
int l = 0, r = -1;
Object[] ans = new Object[quer.size()];
for(int[] a: quer) {
if(r < a[0] || l > a[1]) {
for(int i = l; i<=r; i++) rem.rem(def, nums[i], true);
for(int i = a[0]; i<=a[1]; i++) add.add(def, nums[i], false);
}else {
if(l > a[0]) for(int i = l-1; i>=a[0]; i--) add.add(def, nums[i], true);
else for(int i = l; i<a[0]; i++) rem.rem(def, nums[i], true);
if(r > a[1]) for(int i = r; i>a[1]; i--) rem.rem(def, nums[i], false);
else for(int i = r+1; i<=a[1]; i++) add.add(def, nums[i], false);
}
l = a[0];
r = a[1];
ans[a[2]] = get.get(def);
}
return ans;
}
}
// combiners used for later
public interface Comb<Val>{Val oper(Val left, Val right);}
public interface Prop<Val, Lz> {Val oper(Lz top, Val current, long len);}
public interface LZ<Lz>{Lz oper(Lz top, Lz current);}
public interface Def<Val>{Val get(long len);}
public interface DefLz<Lz>{Lz get();}
// convex hull trick
private static class CHT<T> {
private List<Line<T>> lines;
private boolean max;
public CHT(boolean max) {
this.lines = new ArrayList<>();
this.max = max;
}
public boolean isEmpty() {return lines.isEmpty();}
public void add(long m, long b) {add(m, b, null);}
public void add(long m, long b, T curr) {
if(max) {
m*=-1;
b*=-1;
}
Line line = new Line(m, b, curr);
while (lines.size() >= 2) {
Line l1 = lines.get(lines.size() - 1);
Line l2 = lines.get(lines.size() - 2);
if (BigInteger.valueOf(l1.b-l2.b).multiply(BigInteger.valueOf(l1.m-line.m))
.compareTo(BigInteger.valueOf(line.b-l1.b).multiply(BigInteger.valueOf(l2.m-l1.m))) == 1)
lines.remove(lines.size() - 1);
else break;
}
lines.add(line);
}
public Two<Long, T> get(long x) {
int lo = 0, hi = lines.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (lines.get(mid).yValue(x) < lines.get(mid + 1).yValue(x))
hi = mid;
else lo = mid + 1;
}
return new Two<>((max ? -1:1)*lines.get(lo).yValue(x), lines.get(lo).get());
}
private static class Line<T> {
private long m;
private long b;
private T curr;
public Line(long m, long b, T curr) {
this.m = m;
this.b = b;
this.curr = curr;
}
public T get(){
return curr;
}
public long yValue(long x) {
return m * x + b;
}
}
}
// normal segment tree with all associative operations
private static class AST<Val> {
private class Node<Val> {
public Val val;
public Node<Val> p, le, ri;
public int l, r;
public Node(int l, int r) {
this.l = l;
this.r = r;
}
}
private final Comb<Val> oper;
private final Node<Val> top;
private final Node<Val>[] last;
public AST(int n, Comb<Val> oper) {
this.oper = oper;
top = new Node<>(0, n - 1);
last = new Node[n];
getNode(top);
}
private void getNode(Node<Val> t) {
if (t.l == t.r) {
last[t.l] = t;
return;
}
int mid = (t.l + t.r) >> 1;
t.le = new Node<>(t.l, mid);
t.ri = new Node<>(mid + 1, t.r);
getNode(t.le);
getNode(t.ri);
t.le.p = t.ri.p = t;
}
public void set(int k, Val num) {
Node<Val> t = last[k];
t.val = num;
t = t.p;
while (t != null) {
if (t.le.val != null && t.ri.val != null)
t.val = oper.oper(t.le.val, t.ri.val);
else return;
t = t.p;
}
}
public Val all() {
return top.val;
}
public Val get(int a) {
return last[a].val;
}
public Val get(int a, int b) {
if (a == b)
return get(a);
return get(a, b, top);
}
private Val get(int a, int b, Node<Val> n) {
if (a == n.l && b == n.r)
return n.val;
Node<Val> l = n.le, r = n.ri;
if (l.l <= a && l.r >= b)
return get(a, b, l);
if (r.l <= a && r.r >= b)
return get(a, b, r);
Val left = get(a, l.r, l), right = get(r.l, b, r);
return oper.oper(left, right);
}
}
// binary indexed tree (just sum)
private static class BIT {
private final long[] bit;
private final long[] arr;
private final int len;
private long all;
public BIT(int len) {
bit = new long[len + 1];
arr = new long[len];
this.len = len;
all = 0;
}
public long get(int ind) {
return arr[ind];
}
public void set(int ind, long val) {
add(ind, val - arr[ind]);
}
public void add(int ind, long val) {
all+=val;
arr[ind] += val;
ind++;
for (; ind <= len; ind += ind & -ind)
bit[ind] += val;
}
public long suf(int ind) {
return all-(ind == 0 ? 0:prev(ind-1));
}
public long prev(int ind) {
if(ind == len-1) return all;
ind++;
long sum = 0;
for (; ind > 0; ind -= ind & -ind)
sum += bit[ind];
return sum;
}
public long sum(int a, int b) {
return prev(b) - (a == 0 ? 0 : prev(a - 1));
}
@Override
public String toString() {
StringBuilder ret = new StringBuilder();
ret.append("[");
for(int i = 0; i<len; i++) ret.append(get(i)+(i == len-1 ? "]":", "));
return ret.toString();
}
}
// static range queries (logn preprocessing, constant query)
private static class SRQ<T> {
private static int lg(int n) { return 31 - Integer.numberOfLeadingZeros(n); }
private T[][] data;
private T[] nums;
private Comb<T> oper;
public SRQ(T[] nums, Comb<T> oper) {
this.nums = nums;
this.oper = oper;
int n = nums.length;
int logn = lg(n) + 1;
data = (T[][]) new Object[logn][n];
for(int k = 1; k <= n; k++) {
int rad = 1, i = 0;
while(k % (2 * rad) == 0) {
rad *= 2;
i++;
}
data[i][k - 1] = nums[k - 1];
for(int j = k - 2; j >= k - rad; j--)
data[i][j] = oper.oper(nums[j], data[i][j + 1]);
if(k < n) data[i][k] = nums[k];
for(int j = k + 1; j < n && j < k + rad; j++)
data[i][j] = oper.oper(data[i][j - 1], nums[j]);
}
}
public T get(int l, int r) {
if(l == r) return nums[l];
int ind = lg(l^r);
return oper.oper(data[ind][l], data[ind][r]);
}
}
// normal segment tree (order dosen't matter)
private static class ST {
public interface Oper {
long solve(long a, long b);
}
private long[] tree;
public final int n;
private final Oper oper;
private final int def;
public ST(int n, Oper oper, int def) {
this.n = n;
tree = new long[n << 1];
this.oper = oper;
this.def = def;
for (int i = 0; i < n; i++)
set(i, def);
}
public ST(int n, Oper oper) {
this(n, oper, 0);
}
public ST(int n) {
this(n, (a, b) -> Math.min(a, b), 0);
}
public long get(int a, int b) {
if (a == b)
return tree[a + n];
if (b < a)
return def;
a += n;
b += n;
long curr = 0;
boolean checked = false;
while (a <= b) {
if ((a & 1) == 1) {
if (checked)
curr = oper.solve(curr, tree[a++]);
else
curr = tree[a++];
checked = true;
}
if ((b & 1) == 0) {
if (checked)
curr = oper.solve(curr, tree[b--]);
else
curr = tree[b--];
checked = true;
}
a = a >> 1;
b = b >> 1;
}
return curr;
}
public long all() {
return get(0, n-1);
}
public void set(int index, long val) {
index += n;
tree[index] = val;
for (index = index >> 1; index >= 1; index = index >> 1)
tree[index] = oper.solve(tree[index << 1], tree[(index << 1) + 1]);
}
public long get(int index) {
return tree[index + n];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < n; i++) {
sb.append(get(i));
if (i != n - 1)
sb.append(", ");
}
sb.append("]");
return sb.toString();
}
}
// FastIO reader
private static class FastIO {
InputStream dis;
byte[] buffer = new byte[500007];
int pointer = 0, end = 0;
public FastIO(String fileName) throws Exception {
dis = new FileInputStream(fileName);
}
public char nextChar() throws Exception {
return next().charAt(0);
}
public FastIO(InputStream is) throws Exception {
dis = is;
}
public int nextInt() throws Exception {
int ret = 0;
byte b;
do {
b = nextByte();
} while (b <= ' ');
boolean negative = false;
if (b == '-') {
negative = true;
b = nextByte();
}
while (b >= '0' && b <= '9') {
ret = 10 * ret + b - '0';
b = nextByte();
}
return (negative) ? -ret : ret;
}
public long nextLong() throws Exception {
long ret = 0;
byte b;
do {
b = nextByte();
} while (b <= ' ');
boolean negative = false;
if (b == '-') {
negative = true;
b = nextByte();
}
while (b >= '0' && b <= '9') {
ret = 10 * ret + b - '0';
b = nextByte();
}
return (negative) ? -ret : ret;
}
private byte nextByte() throws Exception {
while (pointer >= end) {
end = dis.read(buffer, 0, buffer.length);
pointer = 0;
}
return buffer[pointer++];
}
public double nextDouble() throws Exception {
return Double.parseDouble(next());
}
public String next() throws Exception {
StringBuffer ret = new StringBuffer();
byte b;
do {
b = nextByte();
} while (b <= ' ');
while (b > ' ') {
ret.appendCodePoint(b);
b = nextByte();
}
return ret.toString();
}
public long[] longArr(int len) throws Exception{
long[] ans = new long[len];
for (int i = 0; i < len; i++)
ans[i] = nextLong();
return ans;
}
public int[] nextArr() throws Exception {
return nextArr(nextInt());
}
public int[] nextArr(int len) throws Exception {
int[] ans = new int[len];
for (int i = 0; i < len; i++)
ans[i] = nextInt();
return ans;
}
public List<Integer>[] nextTree() throws Exception {
return nextTree(nextInt());
}
public LinkedList<Integer>[] nextTree(int n) throws Exception {
return nextGraph(n, n - 1);
}
public LinkedList<int[]>[] weightGraph(int n, int m) throws Exception{
return weightGraph(n, m, false);
}
public LinkedList<int[]>[] weightGraph(int n, int m, boolean directed) throws Exception {
LinkedList<int[]>[] ans = new LinkedList[n];
for(int i = 0; i<n; i++) ans[i] = new LinkedList<>();
for(int i = 0; i<m; i++) {
int a = nextInt()-1, b = nextInt()-1, w = nextInt();
ans[a].add(new int[] {b, w});
if(!directed) ans[b].add(new int[] {a, w});
}
return ans;
}
public LinkedList<Integer>[] nextGraph(int n, int m) throws Exception {
return nextGraph(n, m, false);
}
public LinkedList<Integer>[] nextGraph(int n, int m, boolean directed) throws Exception {
LinkedList<Integer>[] ans = new LinkedList[n];
for (int i = 0; i < n; i++)
ans[i] = new LinkedList<>();
for (int i = 0; i < m; i++) {
int a = nextInt() - 1, b = nextInt() - 1;
ans[a].add(b);
if(!directed) ans[b].add(a);
}
return ans;
}
public char[] chars() throws Exception {
return next().toCharArray();
}
}
}