akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main()
{
    int h, w;
    
    while(cin >> h >> w && h && w) {
        while(h--) {
            int w0 = w;
            while(w0--) cout << '#';
            cout << '\n';
        }
        cout << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3092
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			// 文字列の入力
			String s = sc.next();
			if (s.equals("SUN")) {
				System.out.println(7);
			} else if (s.equals("MON")) {
				System.out.println(6);
			} else if (s.equals("TUE")) {
				System.out.println(5);
			} else if (s.equals("WED")) {
				System.out.println(4);
			} else if (s.equals("THU")) {
				System.out.println(3);
			} else if (s.equals("FRI")) {
				System.out.println(2);
			} else if (s.equals("SAT")) {
				System.out.println(1);
			}
		}
	}
}


Measured memory_bytes: 21844
import itertools

N=int(input())
P=tuple(map(int, input().split()))
Q=tuple(map(int, input().split()))

A=list(itertools.permutations(range(1,N+1)))
#print(A)
pindex=A.index(P)+1
qindex=A.index(Q)+1

print(abs(pindex-qindex))


Measured memory_bytes: 8052
using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
	class Program
	{
		static void Main(string[] args)
		{
			var input = Console.ReadLine().Split(' ');
			int p = int.Parse(input[0]);
			int q = int.Parse(input[1]);
			int r = int.Parse(input[2]);

			var list = new List<int>() { p, q, r };
			list.Sort();
			Console.WriteLine(list[0] + list[1]);
		}
	}
}


Measured memory_bytes: 13140
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

using namespace std;

int gcd(int n, int m) {
    if (n == 0)
        return m;
    return gcd(m % n, n);
}

int bit_count(int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

int main() {
    int n, q;
    string s;
    cin >> n >> q >> s;
    vector<int> answers(n);

    char state = '\0';
    int count = 0;
    for (size_t i = 0; i < n; i++) {
        if (s[i] == 'C' && state == 'A') {
            count++;
        }
        state = s[i];
        answers[i] = count;
    }

    for (size_t i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;

        cout << answers[r - 1] - answers[l - 1] << endl;
    }
}


Measured memory_bytes: 1408
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  int n,k; cin >> n >> k;
  vector<ll> a(n);
  vector<ll> b(0);
  vector<ll> c(0);
  rep(i,n){
    cin >> a[i];
    if(a[i]<0) b.push_back(a[i]);
    else c.push_back(a[i]);
  }
  sort(all(b));
  sort(all(c));
  reverse(all(c));
  if(k==n){
    ll ans=1;
    rep(i,n){
      ans=(ans*a[i])%mod;
    }
    cout << (ans+mod)%mod << endl;
    return 0;
  }
  if(k%2==1&&c.empty()){
    ll ans=1;
    for(int i=n-1;i>n-1-k;i--){
      ans=(ans*b[i])%mod;
    }
    cout << (ans+mod)%mod << endl;
    return 0;
  }
  ll ans=1;
  int K=0;
  if(k%2==1){
    ans=c[0];
    c.erase(c.begin());
    K++;
    if(K==k){
      cout << ans << endl;
      return 0;
    }
  }
  vector<ll> pm(0);
  for(int i=0;i<b.size();i+=2){
    if(i+1>=b.size()) break;
    pm.push_back(b[i]*b[i+1]);
  }
  for(int i=0;i<c.size();i+=2){
    if(i+1>=c.size()) break;
    pm.push_back(c[i]*c[i+1]);
  }
  sort(all(pm));
  reverse(all(pm));
  for(int i=0;;i++){
    ans=(ans*(pm[i]%mod))%mod;
    K+=2;
    if(K==k) break;
  }
  cout << ans << endl;
}


Measured memory_bytes: 8292
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <limits>
#include <cmath>
#include <iomanip>
#include <functional>
#include <random>
#include <set>
using namespace std;
using ll = long long;

using namespace std;

const ll INF = numeric_limits<ll>::max();
struct LazySegmentTree
{
private:
    ll n;
    vector<ll> node, lazy;
    vector<bool> lazyFlag;

public:
    LazySegmentTree(vector<ll> v)
    {
        ll sz = (ll)v.size();
        n = 1;
        while (n < sz)
            n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, INF);
        lazyFlag.resize(2 * n - 1, false);

        for (ll i = 0; i < sz; i++)
            node[i + n - 1] = v[i];
        for (ll i = n - 2; i >= 0; i--)
            node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);
    }

    void lazyEvaluate(ll k, ll l, ll r)
    {
        if (lazyFlag[k])
        {
            //ここ修正
            node[k] = min(lazy[k], node[k]);
            if (r - l > 1)
            {
                //ここ修正
                lazy[k * 2 + 1] = min(lazy[k], lazy[k * 2 + 1]);
                lazy[k * 2 + 2] = min(lazy[k], lazy[k * 2 + 2]);
                lazyFlag[k * 2 + 1] = lazyFlag[k * 2 + 2] = true;
            }
            lazyFlag[k] = false;
        }
    }

    void update(ll a, ll b, ll x, ll k = 0, ll l = 0, ll r = -1)
    {
        if (r < 0)
            r = n;
        lazyEvaluate(k, l, r);
        if (b <= l || r <= a)
            return;
        if (a <= l && r <= b)
        {
            //ここ修正
            lazy[k] = min(lazy[k], x);
            lazyFlag[k] = true;
            lazyEvaluate(k, l, r);
        }
        else
        {
            update(a, b, x, 2 * k + 1, l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = min(node[2 * k + 1], node[2 * k + 2]);
        }
    }

    ll find(ll a, ll b, ll k = 0, ll l = 0, ll r = -1)
    {
        if (r < 0)
            r = n;
        lazyEvaluate(k, l, r);
        if (b <= l || r <= a)
            return INF;
        if (a <= l && r <= b)
            return node[k];
        ll vl = find(a, b, 2 * k + 1, l, (l + r) / 2);
        ll vr = find(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};

int main()
{
    // 整数の入力
    ll N, Q;
    cin >> N >> Q;
    vector<ll> A(N - 2, N - 2);
    ll ans = (N - 2) * (N - 2);
    LazySegmentTree vertical(A);
    LazySegmentTree horizontal(A);
    for (int i = 0; i < Q; i++)
    {
        ll t, x;
        cin >> t >> x;
        x -= 2;
        if (t == 1)
        {
            ll depth = vertical.find(x, x + 1);
            // cout << depth << endl;
            ans -= depth;
            horizontal.update(0, depth, x);
        }
        else
        {
            ll depth = horizontal.find(x, x + 1);
            // cout << depth << endl;
            ans -= depth;
            vertical.update(0, depth, x);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 23008
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let mut cnt: Vec<i64> = vec![0; 100_001];
    let mut sum: i64 = 0;
    for _ in 0..n {
        let ai: usize = read();
        sum += ai as i64;
        cnt[ai] += 1;
    }

    let q: usize = read();
    let mut bc: Vec<(i64, i64)> = vec![];

    for _ in 0..q {
        let b: i64 = read();
        let c: i64 = read();
        bc.push((b, c));
    }

    for i in 0..q {
        let bci = bc[i];
        let b = bci.0;
        let c = bci.1;
        sum += ((c - b) * cnt[b as usize] as i64);
        cnt[c as usize] += cnt[b as usize];
        cnt[b as usize] = 0;
        println!("{}", sum);
    }
}


Measured memory_bytes: 4436
#include <bits/stdc++.h>
using namespace std;

long long sum(long long n) {
    
    return n*(n+1)/2;
}

int main() {
	
    int n;
  	cin>>n;
    long long sm;

    sm = sum(n)-3*sum(n/3)-5*sum(n/5)+15*sum(n/15);

    printf("%lld",sm);

}

Measured memory_bytes: 3760
class Bit:
  def __init__(self, n):
    self.size = n
    self.tree = [0] * (n + 1)
 
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self, i, x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

from itertools import accumulate
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = [int(input())-k for i in range(n)]
acc = [0]+list(accumulate(a))
acc_i = []
for i,x in enumerate(acc):
  acc_i.append((x,i+1))
acc_i.sort()
bit = Bit(n+2)
ans = 0
for i in range(n+1):
  x = acc_i[i][1]
  ans += n+1-x+bit.sum(x)
  bit.add(1,-1)
  bit.add(x+1,1)
print(ans)

Measured memory_bytes: 73256
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,x;
int defrag;
int defragg;
bool dis[10]= {};
cin>>n>>x;
for(int i=0;i<x;i++){
    cin>>defrag;
    dis[defrag]=1;
}
for(int i=n;i;i++){
    defrag=i;
    int o=0;
    while(defrag>0){
        defragg=defrag%10;
        defrag/=10;
        if(dis[defragg]==1){
            o=1;
            break;
        }
    }
    if(o==1){
        continue;
    }
    else{
        cout<<i;
        break;
    }
}
}


Measured memory_bytes: 3592
#include<iostream>
 
using namespace std;
int main()
 
{
int r;
cin>>r;
 
if(r<1200){
    cout<<"ABC"<<endl;
 
}
 
else if(r<2800){
    cout<<"ARC"<<endl;
}
else{
        cout<<"AGC"<<endl;
 
}
return 0;
 
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        for(int i=1;i<361;i++){
            if(x * i % 360 == 0){
                System.out.println(i);
                break;
            }
        }
    }
}


Measured memory_bytes: 26944
h,w = map(int, input().split())
alp_d = {chr(ord('a') + i): 0 for i in range(26)}

for _ in range(h):
    s = list(input())
    for si in s:
        alp_d[si] += 1
        alp_d[si] %= 4

r4 = [0]*4
for v in alp_d.values():
    r4[v] += 1

if w%2 == 0 and h%2 == 0:
    if r4[1] == 0 and r4[2] == 0 and r4[3] == 0 and r4[0] > 0:
        print('Yes')
    else:
        print('No')

elif w%2 == 0 and h%2 != 0:
    if r4[1] == 0 and r4[2] <= w//2 and r4[3] == 0:
        print('Yes')
    else:
        print('No')

elif h%2 == 0 and w%2 != 0:
    if r4[1] == 0 and r4[2] <= h//2 and r4[3] == 0:
        print('Yes')
    else:
        print('No')       

else:
    cnt2 = (w-1)//2 + (h-1)//2
    if r4[1] == 1 and r4[2] <= cnt2 and r4[3] == 0:
        print('Yes')
    elif r4[1] == 0 and r4[2] <= cnt2-1 and r4[3] == 1:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 65568
<?php

fscanf(STDIN, "%d %d", $n, $m);
$A = [];
for ($i = 0; $i < $n; ++$i) {
    fscanf(STDIN, "%d %d", $a, $b);
    $A[$m - $a][] = $b;
}

$sum = 0;
$pq = new SplPriorityQueue();
for ($i = $m - 1; $i >= 0; --$i) {
    // i日目にできる仕事は$A[$i]
    if (isset($A[$i])) {
        foreach ($A[$i] as $val) {
            $pq->insert($val, $val);
        }
    }

    if ($pq->valid()) {
        $sum += $pq->extract();
    }
}

echo $sum;


Measured memory_bytes: 55800
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
const ll mod = 1000000007;
const ll INF = 9223372036854775807;
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define Pi acos(-1)

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << setprecision(15) << fixed;
  ll a, b;
  cin >> a >> b;
  cout << max({a+b,a-b,a*b}) << '\n';
}

Measured memory_bytes: 3624
#include"bits/stdc++.h"


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 200010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n;

int A[maxn];

void Work(){
	ll l=2,r=2;
	RREP(i,n,1){
		if((l-1)/A[i]==r/A[i]){
			puts("-1");
			return;
		}
		ll tl=((l-1)/A[i]+1)*A[i];
		ll tr=(r/A[i]+1)*A[i]-1;
		l=tl;r=tr;
	}
	cout<<l<<' '<<r<<endl;
}

void Init(){
	read(n);
	REP(i,1,n)read(A[i]);
}

int main(){
	Init();
	Work();
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 16;
typedef long long ll;
ll a[maxn][maxn];
ll dp[1<<maxn];
int main()
{
//    freopen("in", "r", stdin);
    int n;
    cin>>n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
            cin>>a[i][j];
    }
    for(int S = 0; S < (1 << n); S++){
        for(int i = 0; i < n; i++){
            if(((S>>i)&1) == 0)continue;
            for(int j = i+1; j < n; j++){
                if(((S>>j)&1) == 0)continue;
                dp[S] += a[i][j];
            }
        }
    }
    for(int S = 0; S < (1 << n); S++){
        for(int S0 = S; S0; S0 = (S0 - 1)&S){
            dp[S] = max(dp[S], dp[S0] + dp[S^S0]);
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
    return 0;
}


Measured memory_bytes: 768
#include<iostream>
#include<vector>
#include<string>
using namespace std;
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
int main(){
  string s;
  cin>>s;
  int co[260]={0};
  rep(i,s.size())co[s[i]]++;
  int out=0;
  rep(i,260){
    if(co[i]){
      int cnt=0;
      int j=i;
      while(co[j])j++;
      if(j-i<3){
	out++;
	co[i]--;
      }else{
	out+=3;
	loop(k,i,j)co[k]--;
      }
      i--;
    }
  }
  cout<<out<<endl;
}

Measured memory_bytes: 1188
def main():
    import math

    n = int(input())
    x, y = n / 1.08, (n + 1) / 1.08
    a, b = math.floor(x), math.ceil(y)

    for i in range(a, b):
        if math.floor(1.08 * i) == n:
            print(i)
            break
    else:
        print(':(')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;

	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int c = 0; c < n; c++) {
			double x1 = sc.nextDouble(), y1 = sc.nextDouble(), r1 = sc.nextDouble();
			double x2 = sc.nextDouble(), y2 = sc.nextDouble(), r2 = sc.nextDouble();
			double dx = abs(x1 - x2), dy = abs(y1 - y2), rp = r1 + r2;
			if( dx * dx + dy * dy > rp * rp ) { System.out.println(0); continue; }
			if( sqrt( dx * dx + dy * dy ) + r1 < r2 )
			{ System.out.println(-2); continue; }
			if( sqrt( dx * dx + dy * dy ) + r2 < r1 )
			{ System.out.println(2); continue; }
			System.out.println(1);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

Measured memory_bytes: 12000
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
vector<vector<int>>go;
vector<llint>fra;
vector<llint>dfs(int ter,int per){
	vector<llint>ans={0,1};
	for(auto it:go[ter]){
		if(it==per){continue;}
		auto ret=dfs(it,ter);
		int i,j,x=ans.size(),y=ret.size();
		vector<llint>iti(x+y-1);
		for(i=0;i<x;i++){
			for(j=0;j<y;j++){
				iti[i+j]+=ans[i]*ret[j];
				iti[i+j]%=mod;
			}
		}
		ans=iti;
	}
	for(int i=0;i<ans.size();i+=2){
		ans[0]-=ans[i]*fra[i/2];
		ans[0]%=mod;
	}
	return ans;
}
int main(void){
	int n,i;cin>>n;
	go.res(n);
	fra.res(n/2 +1);
	fra[0]=1;
	for(i=1;i<=n/2;i++){fra[i]=fra[i-1]*(2*i-1)%mod;}
	for(i=0;i<n-1;i++){
		int a,b;cin>>a>>b;a--;b--;
		go[a].pub(b);
		go[b].pub(a);
	}
	cout<<(mod-dfs(0,-1)[0])%mod<<endl;
	return 0;
}



Measured memory_bytes: 1408
s = input()
tmp1 = ""
tmp2 = ""
for i in range(len(s)):
    if i %2 ==0:
        tmp1+=str(1)
    else:
        tmp1+=str(0)

for i in range(len(s)):
    if i %2 ==0:
        tmp2+=str(0)
    else:
        tmp2+=str(1)
        
count1=0
count2=0
for i in range(len(s)):
    if s[i] != tmp1[i]:
        count1+=1
        
for i in range(len(s)):
    if s[i] != tmp2[i]:
        count2+=1
        
print(min(count1, count2))

Measured memory_bytes: 3316
#include <iostream>

const int N = 55;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

#if DEBUG_ON
    freopen("input", "r", stdin);
#endif

    int n, a, arr[N];
    std::cin >> n >> a;
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }
    long long dp[N][N][N * N] = { 0 };
    for (int i = 1; i <= n; ++i) {
        ++dp[i][1][arr[i - 1]];
        for (int k = 0; k < N * N; ++k) {
            dp[i][1][k] += dp[i - 1][1][k];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 2; j <= i; ++j) {
            for (int k = 0; k < N * N; ++k) {
                dp[i][j][k] = dp[i - 1][j][k];
                if (k >= arr[i - 1]) {
                    dp[i][j][k] += dp[i - 1][j - 1][k - arr[i - 1]];
                }
            }
        }
    }
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        res += dp[n][i][a * i];
    }
    std::cout << res << '\n';
    return 0;
}

Measured memory_bytes: 71808
#include <iostream>
using namespace std;

int main() {
	string a,b,c;
	cin>>a>>b>>c;
	int turn = 0;
	int i=0,j=0,k=0;
	while(1)
	{
		if(turn == 0)
		{
			if(a[i]=='\0'){cout<<"A"<<endl;break;}
			turn = a[i]-'a';
			i++;
		}
		else if(turn == 1)
		{
			if(b[j]=='\0'){cout<<"B"<<endl;break;}
			turn = b[j]-'a';
			j++;
		}
		else if(turn == 2)
		{
			if(c[k]=='\0'){cout<<"C"<<endl;break;}
			turn = c[k]-'a';
			k++;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
typedef P <int, int> Pii;
int main( void ){
	// initialize();
	int H, W;
	cin >> H >> W;
	vector <vector <P <int, bool> > > maze( H, vector <P <int, bool> >( W, P <int, bool>{-1, false} ));
	int cnt = 0;
	rep( i, 0, H ){
		rep( j, 0, W ){
			char s; cin >> s;
			maze[ i ][ j ].b = ( s == '.' );
			if (maze[ i ][ j ].b)
				cnt++;
		}
	}
	maze[ 0 ][ 0 ].a = 1;
	queue <Pii> q;
	q.push( Pii{0, 0} );
	while(!q.empty()){
		const int vect[ 4 ][ 2 ] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1} };
		int dist = maze[ q.front().a ][ q.front().b ].a + 1;
		rep( i, 0, 4 ){
			int x = q.front().a + vect[ i ][ 0 ], y = q.front().b + vect[ i ][ 1 ];
			if (y < 0 || x < 0 || x == H || y == W ){
				continue;
			}
			if (!maze[ x ][ y ].b){
				continue;
			}
			if (maze[ x ][ y ].a == -1){
				maze[ x ][ y ].a = dist;
				q.push( Pii{x, y} );
				maze[ x ][ y ].b = false;
			}
		}
		q.pop();
	}
	int ans = cnt - maze[ H - 1 ][ W - 1 ].a;
	if (maze[ H - 1 ][ W - 1 ].a == -1)
		ans = -1;
	cout << ans << endl;
}

template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iterator>
#include<math.h>

using namespace std;
#define int long long
/*                      */    //#undef int
#define INF 1000000009
#define INFL 1000000000000000018ll
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define mk(a, b) make_pair(a, b)
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef priority_queue<PA, vector<PA>, greater<PA> >PQG;

int par[100005], rrank[100005];
int n, m, a[100005];

void init(int n_)
{
    for(int i = 0; i <= n_; i++){
        par[i] = i;
    }
}

int root(int x)
{
    if(x == par[x]){
        return x;
    }
    else{
        return par[x] = root(par[x]);
    }
}

void unite(int x, int y)
{
    x = root(x), y = root(y);
    if(x == y)return;

    if(rrank[x] < rrank[y]){
        par[x] = y;
    }
    else{
        par[y] = x;
        if(rrank[x] == rrank[y]){
            rrank[x]++;
        }
    }
}

bool same(int x, int y)
{
    return root(x) == root(y);
}

signed main()
{
    cin >> n >> m;
    init(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < m; i++){
        int l, r;
        cin >> l >> r;
        unite(l, r);
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(same(i + 1, a[i])){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 2560
import sys
sys.setrecursionlimit(9**9)
n=int(input())
T=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a-1].append([b-1,i])
C=[0]*(n-1)
def f(i,r):
    c=1
    for (x,y) in T[i]:
        c+=(c==r)
        C[y]=c
        f(x,c)
        c+=1
f(0,0)
print(max(C))
for c in C:
    print(c)

Measured memory_bytes: 70996
L, R = list(map(int, input().split()))

if (R-L) > 2018:
    print(0)
else:
    mini = 2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            mini = min(mini, (i*j)%2019)
    print(mini)


Measured memory_bytes: 2940
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    K_bin = bin(K)[2:]
    AB=LLIN(N)

    ans = 0
    for a,b in AB:
        if a&K==a:
            ans += b

    for i in range(len(K_bin)):
        if K_bin[i]=="0":
            continue
        i_inv = len(K_bin)-(i+1)
        res = 0
        k = K - (1<<i_inv)
        for a,b in AB:
            left_a = (a>>i_inv<<i_inv) #上位i+1bit            
            if left_a&k==left_a:
                res += b
            else:
                continue
        ans = max(ans, res)
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 82648
#include<bits/stdc++.h>
using namespace std;

bool wall[2][103]={};
int wallnum[2][101];

int serch(int n,int now,int num,int co)
{
    if(wall[now][num])return -1;
    wall[now][num]=1;
    if(num>=n-1)return co;
    if(wallnum[now][num]==0||wallnum[now][num]==1&&wallnum[now][num+1]!=1){
        now++;
        if(now>1)now=0;
        for(int i=2;i>0;i--)if(wallnum[now][num+i]!=2)return serch(n,now,num+i,co+1);
        return serch(n,now,num,co+1);
    }
    else if(wallnum[now][num]==1)return serch(n,now,num+1,co);
    else return serch(n,now,num-1,co);
}
int main()
{
    int n;
    while(cin>>n,n){

        for(int i=0;i<2;i++){
            for(int j=0;j<n;j++)cin>>wallnum[i][j];
        }
        int ans[2];
        for(int i=0;i<2;i++){
            memset(wall,0,sizeof(wall));
            ans[i]=serch(n,i,0,0);
        }
        if(ans[0]==-1&&ans[1]==-1)cout<<"NA\n";
        else if(ans[0]==-1||ans[1]==-1)cout<<max(ans[0],ans[1])<<endl;
        else cout<<min(ans[0],ans[1])<<endl;
    }
}

Measured memory_bytes: 1164
# https://atcoder.jp/contests/agc022/submissions/9146869

s = str(input())

# 英小文字26個
alphabet = set(chr(ord('a')+i) for i in range(26))

def F_short(s):
  # 未使用の文字で最小のものを後ろに付ける
  se = alphabet - set(s)
  x = min(se)
  return s + x

def F_long(s):
  # 辞書順いちばん最後 zyx...cba
  if s == ''.join(sorted(alphabet, reverse=True)):
    return -1

  # 1文字ずつpopして、増加チャンスを待つ
  cand = []  # 末尾から除去した文字たち
  s = list(s)
  while True:
    x = s[-1]  # 末尾の文字
    if (not cand) or (x > max(cand)):
      cand.append(s.pop())
      continue
    else:
      break
  y = min(ch for ch in cand if ch > x)
  return ''.join(s[:-1]) + y

if len(s) < 26:
  ans = F_short(s)
else:
  ans = F_long(s)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
typedef tuple<ll, ll, ll> T;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,c;
    cin>>n>>m>>c;
    vector<int> B(m);
    REP(i,m) cin>>B[i];
    int ans=0;
    REP(i,n){
        ll sum=0;
        REP(j,m){
            int a;cin>>a;
            sum+=B[j]*a;
        }
        if(sum+c>0) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <string>
#include <utility>
#include <map>
#include <vector>
#include <iostream>
using namespace std;

const int alph = 26;
int main() {
    string s, t; cin >> s >> t;
    if(s.length() > t.length()) swap(s, t);
    for(int len=s.length(); len>=1; len--) {
        vector<int> vec(alph);
        for(int i=0; i<len-1; i++) {
            vec[ s[i] - 'a' ]++;
        }

        map< vector<int>, int > mp;
        for(int i=len-1; i<(int)s.length(); i++) {
            vec[ s[i] - 'a' ]++;
            mp[vec]++;
            vec[ s[i-len+1] - 'a' ]--;
        }

        vec = vector<int>(alph);
        for(int i=0; i<len-1; i++) {
            vec[ t[i] - 'a' ]++;
        }
        for(int i=len-1; i<(int)t.length(); i++) {
            vec[ t[i] - 'a' ]++;
            if(mp.count(vec)) {
                cout << len << endl;
                return 0;
            }
            vec[ t[i-len+1] - 'a' ]--;
        }
    }
    cout << 0 << endl;
    return 0;
}


Measured memory_bytes: 3928
n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [10**9]*(n+1)
dp[0] = 0
for i in range(1,n):
    K = k if i >= k else i
    for j in range(1,K+1):
        t = dp[i-j] + abs(h[i-j]-h[i])
        if dp[i] > t:
            dp[i] = t
# print(dp)
print(dp[n-1])

Measured memory_bytes: 52448
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pll pair<ll,ll>
#define sll set<ll>
#define msll multiset<ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define vpl vector<pll>
#define gll greater<ll>
#define gpl greater<pll>
#define spl set<pll>
#define mspl multiset<pll>
#define lb lower_bound
#define bp __builtin_popcount
#define ub upper_bound
#define prq priority_queue
#define mp make_pair
#define pb push_back
#define mem(x,y) memset(x, y, sizeof x)
#define endl "\n"
#define sz(x) (ll)x.size()
#define sqr(x) x*x
#define rapido ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef long double ld;
ll mx = INT_MAX;
ll mn = INT_MIN;
ll INF = 1e18+10;
ll MOD = 1e9+7;
const ll maxs = (1<<11);
const ll lg = 22; 
ll fast(ll base , ll expo){ ll res = 1; while(expo>=1){ if(expo%2) res *= base; base *= base; expo /= 2; } return res; }

ll R,C,K;
string S[6];

void init(){
    mx = INT_MIN; mn = INT_MAX; INF = 1e18+10;
}

void code_idhr_h(){
    ll N; cin>>N;
    ll A[N+1];
    for(ll i=1; i<=N; i++) cin>>A[i];
    if(N==1){
        cout<<0<<endl;
        return;
    }
    sort(A+1, A+N+1);
    ll ans = 0;  ll cnt = 2;
    for(ll i=N; i>=1; i--){
        if(i==N) ans += A[i];
        else{
            if(cnt==N) break;
            ans += A[i];
            cnt++;
            if(cnt==N) break;
            ans += A[i];
            cnt++;
            if(cnt == N) break;
        }
    }
    cout<<ans<<endl;
}

int main(){
    rapido;
    ll T=1; //cin>>T;
    //pre();
    while(T--){
        init();
        code_idhr_h();
    }
    return 0;
}

Measured memory_bytes: 5220
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int n = 26, d;
	static int[] c, last;
	static int[][] s;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		d = Integer.parseInt(br.readLine());
		String[] sa = br.readLine().split(" ");
		c = new int[n];
		for (int i = 0; i < n; i++) {
			c[i] = Integer.parseInt(sa[i]);
		}
		s = new int[d][n];
		for (int i = 0; i < d; i++) {
			sa = br.readLine().split(" ");
			for (int j = 0; j < n; j++) {
				s[i][j] = Integer.parseInt(sa[j]);
			}
		}
		int[] t = inputB(br);
		br.close();

		last = new int[n];
		int[] manzoku = calc(t);
		for (int i = 0; i < d; i++) {
			System.out.println(manzoku[i]);
		}
	}

	static int[] inputB(BufferedReader br) throws Exception {
		int[] t = new int[d];
		for (int i = 0; i < d; i++) {
			t[i] = Integer.parseInt(br.readLine()) - 1;
		}
		return t;
	}

	static int[] calc(int[] t) {
		int[] ret = new int[d];
		for (int i = 0; i < d; i++) {
			if (i > 0) {
				ret[i] += ret[i - 1];
			}
			ret[i] += s[i][t[i]];
			last[t[i]] = i + 1;
			for (int j = 0; j < n; j++) {
				ret[i] -= c[j] * (i + 1 - last[j]);
			}
		}
		return ret;
	}
}


Measured memory_bytes: 35432
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
    ll n;
    cin >> n;
    ll a[5];
    ll MAX = 0;
    ll up;
    rep(i, 5){
        cin >> a[i];
        if(n % a[i] != 0){
            up = n/a[i] + 1;
        }else{
            up = n/a[i];
        }
        MAX = max(MAX, up);
    }

    cout << 4+MAX << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,k;
    long long int a,b,c,n;
    cin>>a>>b;
    if((a>=1 && a<=9) && (b>=1 && b<=9))
    {
       c=a*b;
       cout<<c<<endl;
    }
    else{
        cout<<"-1"<<endl;
    }
}


Measured memory_bytes: 256
/* code by AbhiTaker  */
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef unsigned long long ull;
#define M 1000000007
#define N 1000016
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
#define f first
#define s second
#define inf 9000000000000000000

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll n,i;
    cin>>n;
    ll a[n+1];
    for(i=0; i<n; i++)
        cin>>a[i];

    sort(a,a+n);
    ll cnt = 1,last = a[0];
    for(i=1; i<n; i++)
    {
        if(a[i]!=last)
        {
            cnt++;
            last=a[i];
        }
    }

    cout<<cnt<<"\n";




    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;
typedef long long int ll;
#define F first
#define S second
#define MP make_pair
const int N=5e5+10;
const ll INF=1LL<<60;
ll dis(pi a,pi b){
    ll x=a.F-b.F,y=a.S-b.S;
    return x*x+y*y;
}
int main(){
    int n,lim;
    ll ans=INF;
    pi a[N];
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d%d",&a[i].F,&a[i].S);
    sort(a,a+n);
    lim=min(25,n);
    for(int i=0;i<lim;i++)for(int j=i+1;j<lim;j++)ans=min(ans,dis(a[i],a[j]));
    for(int i=lim;i<n;i++)for(int j=1;j<lim;j++)ans=min(ans,dis(a[i],a[i-j]));
    printf("%lld\n",ans);
}


Measured memory_bytes: 6656
#include<cstdio> 
#include<algorithm>
#include<cstring>
#include<cmath>
#include<bitset>
#include<set>
using namespace std;
typedef long long ll;
typedef double db;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
const int N=1e8+5,mo=998244353,M=1e5;
struct rec
{
	int x,y;
}a[M];
int sta[M],st,pd[M],dfn[M],low[M],td,tag,d1,d2,d3,d4,k,tb,bel[M],ta,ref[M],v[M],le[M],ri[M],t1,rt;
int l,r,mid,n,i,j,x,y;
int tt,b[N],nxt[N],fst[M];
bool cmp(rec a,rec b)
{
	return a.x<b.x;
}
void cr(int x,int y)
{
	tt++;
	b[tt]=y;
	nxt[tt]=fst[x];
	fst[x]=tt;
}
void tarjan(int x)
{
	sta[++st]=x;
	pd[x]=1;
	low[x]=dfn[x]=++td;
	for(int p=fst[x];p;p=nxt[p])
	{
		if (pd[b[p]]==2) continue;
		if (!pd[b[p]])
		{
			tarjan(b[p]);
			cmin(low[x],low[b[p]]);
		}else
			cmin(low[x],dfn[b[p]]);
	}
	if (dfn[x]==low[x])
	{
		tb++;
		while (sta[st+1]!=x)
		{
			pd[sta[st]]=2;
			bel[sta[st]]=tb;
			st--;
		}
	}
}
void clear()
{
	fo(i,1,t1) sta[i]=pd[i]=fst[i]=bel[i]=low[i]=dfn[i]=0;
	td=tb=tt=0;
}
void make(int x,int l,int r)
{
	if (l==r) return;
	int m=(l+r)/2;
	if (l!=m) le[x]=++t1;else le[x]=ref[a[l].y];
	if (r!=m+1) ri[x]=++t1;else ri[x]=ref[a[r].y];
	cr(x,le[x]);
	cr(x,ri[x]);
	make(le[x],l,m);
	make(ri[x],m+1,r);
}
void link(int x,int l,int r,int i,int j,int p)
{
	if (i>j) return ;
	if (l==i&&r==j)
	{
		cr(a[p].y,x);
		return ;
	}
	int m=(l+r)/2;
	if (m>=j) link(le[x],l,m,i,j,p);
	else if (m<i) link(ri[x],m+1,r,i,j,p);
	else
	{
		link(le[x],l,m,i,m,p);
		link(ri[x],m+1,r,m+1,j,p);
	}
}
int judge(int mid)
{
	int l,r;
	clear();
	t1=ta;
	rt=++t1;
	make(rt,1,ta);
	fo(i,1,ta)
	{
		l=lower_bound(v+1,v+1+ta,v[i]-mid+1)-v;
		r=upper_bound(v+1,v+1+ta,v[i]+mid-1)-v;
		r--;
		link(rt,1,ta,l,i-1,i);
		link(rt,1,ta,i+1,r,i);
	}
	fo(i,1,t1) if (!pd[i])
		tarjan(i);
	fo(i,1,n) if (bel[i*2-1]==bel[i*2]) return 0;
	return 1;
}
int main()
{
	scanf("%d",&n);
	l=0;
	fo(i,1,n) 
	{
		scanf("%d %d",&x,&y);
		a[++ta].x=x;
		a[ta].y=ta;
		ref[ta]=ta+1;
		a[++ta].x=y;
		a[ta].y=ta;
		ref[ta]=ta-1;
		cmax(r,max(x,y));
	}
	sort(a+1,a+1+ta,cmp);
	fo(i,1,ta) v[i]=a[i].x;
	r/=n-1;
	while (l<r)
	{
		mid=(l+r+1)/2;
		if (judge(mid)) l=mid;
		else r=mid-1;
	}
	printf("%d\n",l);
}

Measured memory_bytes: 15616
/*
* @Author: _dp95
* @Date:   2020-03-24 17:27:20
*/
#include "bits/stdc++.h"
using namespace std ;

#define timesaver ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll ;
typedef long double ldb ;

#define mp make_pair
#define pb push_back
#define F first
#define S second
#define nl '\n'

#define all( x ) x.begin(),x.end() 
#define sz( x ) ( int )( x ).size( )
#define mem( a, val ) memset(a, val, sizeof( a ) )
#define deci( x ) cout<<fixed<<setprecision( x );
#define bitcount( x ) __builtin_popcountll( x )

const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

const int MAX = 2*1000*1000 + 10 ;
const ll INF = 1e18 ;
const int MOD = 1e9 + 7 ;

ll n ;
vector< ll > v, sum ;
vector< vector< ll > > dp ;

ll cost( ll l, ll r ){
  return sum[r] - (l?sum[l-1]:0);
} 

ll sol( ll l, ll r ){
  if( l == r )
    return 0 ;
  if( l+1 == r ){
    return cost( l, r ) ;
  }
  ll &ans = dp[l][r] ;
  if( ans != INF )
    return ans ;
  for( ll i = l+1; i <= r ; i++ ){
    ans = min( ans, sol( l, i-1 ) + sol( i, r ) + cost( l, r ) ) ;
  }
  return ans ;
}

int main( ){
  timesaver ;
  cin >> n ;
  v.resize( n );
  sum.resize(n);
  dp.resize( n, vector< ll >( n, INF ) ) ;
  for( ll &i : v )
    cin >> i ;
  partial_sum( all(v), sum.begin() ) ;
  cout << sol( 0, n-1 ) << nl ;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;

int main(){
  int l;
  cin >> l;
  string S;
  cin >> S;
  int ans = 0;
  for(int i = 0; i < l; ++i){
    if(S[i] != '.'){
      continue;
    }
    int i1 = i;
    int i2 = i;
    int h = 0;
    while(1){
      if(i1 == 0){
	break;
      }
      --i1;
      if(S[i1] == 'W'){
	continue;
      }else if(S[i1] == 'B'){
	--h;
	break;
      }else{
	break;
      }
    }
    while(1){
      if(i2 == l - 1){
	break;
      }
      ++i2;
      if(S[i2] == 'W'){
	continue;
      }else if(S[i2] == 'B'){
	--h;
	break;
      }else{
	break;
      }
    }
    if(h == -2){
      continue;
    }
    int for_ = 0;
    int back_ = 0;
    i1 = i;
    i2 = i;
    while(1){
      if(i1 == 0){
	break;
      }
      --i1;
      if(S[i1] == 'B'){
	continue;
      }else if(S[i1] == 'W'){
	back_ = i - i1 - 1;
	break;
      }else{
	break;
      }
    }
    while(1){
      if(i2 == l - 1){
	break;
      }
      ++i2;
      if(S[i2] == 'B'){
	continue;
      }else if(S[i2] == 'W'){
	for_ = i2 - i - 1;
	break;
      }else{
	break;
      }
    }
    ans = max(ans, max(for_, back_));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3212
#include<iostream>
#include<cstdlib>
#include<vector>
#include<algorithm>

#define INF (1<<29)

using namespace std;

template<class T>
struct treap{
  struct node_t{
    T val;
    T sum;
    node_t *lch, *rch;
    int pri;
    int cnt;
    node_t(T v, int p):val(v),pri(p),cnt(1),sum(v){
      lch=rch=NULL;
    }
  };
  node_t *root;
  treap():root(NULL){}

  int count(node_t *t){return t?t->cnt:0; }
  T   sum(node_t *t){return t?t->sum:INF;}
  int size(){return count(root);}

  node_t *update(node_t *t){
    t->cnt=count(t->lch)+count(t->rch)+1;
    t->sum=min(min(sum(t->lch),sum(t->rch)),t->val);
    return t;
  }
  node_t *merge(node_t *l, node_t *r){
    if(!l||!r) return l?l:r;
    if(l->pri>r->pri){
      l->rch=merge(l->rch,r);
      return update(l);
    }
    else{
      r->lch=merge(l,r->lch);
      return update(r);
    }
  }
  pair<node_t*,node_t*> split(node_t *t,int k){
    if(!t) return make_pair((node_t*)NULL,(node_t*)NULL);
    if(k<=count(t->lch)){
      pair<node_t*,node_t*>s=split(t->lch,k);
      t->lch=s.second;
      return make_pair(s.first,update(t));
    }
    else{
      pair<node_t*,node_t*>s=split(t->rch,k-count(t->lch)-1);
      t->rch=s.first;
      return make_pair(update(t),s.second);
    }
  }
  node_t *insert(node_t *t,int k,T val,int pri){
    pair<node_t*, node_t*>s=split(t,k);
    t=merge(s.first, new node_t(val,pri));
    t=merge(t,s.second);
    return update(t);
  }
  node_t *erase(node_t *t,int k){
    pair<node_t*, node_t*>s1,s2;
    s2=split(t,k+1);
    s1=split(s2.first,k);
    t=merge(s1.first,s2.second);
    return update(t);
  }

  node_t *find(node_t *t,int k){
    int c=count(t->lch);
    if(k<c)return find(t->lch, k);
    if(k==c)return t;
    return find(t->rch,k-c-1);
  }

  void insert(int k,T val){root=insert(root,k,val,rand());}
  void erase(int k){root=erase(root,k);}
  node_t *find(int k){return find(root,k);}

  void shift(int l,int r){
    pair<node_t*,node_t*>a,b,c;
    c=split(root,r);
    b=split(c.first,r-1);
    a=split(b.first,l);
    root=merge(a.first,b.second);
    root=merge(root,a.second);
    root=merge(root,c.second);
  }

  int query(int l,int r,node_t *t){
    int sz=count(t);
    if(sz<=l || r<=0)return INF;
    if(l<=0 && sz<=r)return sum(t);

    int c=count(t->lch);
    int vl=query(l,r,t->lch);
    int vr=query(l-c-1,r-c-1,t->rch);
    int res=min(vl,vr);
    if(l<=c && c<r)res=min(res,t->val);
    return res;
  }
};

int main(void){

  srand(time(NULL));
  int n,q;
  treap<int> t;

  cin >> n >> q;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    t.insert(i,a);
  }

  for(int i=0;i<q;i++){
    int x,y,z;
    cin >> x >> y >> z;

    if(x==0)t.shift(y,z+1);
    else if(x==1)cout << t.query(y,z+1,t.root) << endl;
    else if(x==2){
      t.erase(y);
      t.insert(y,z);
    }
  }

  return 0;
}

Measured memory_bytes: 13704
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1001001001;
constexpr long long INFL = (1LL<<60);
constexpr double eps = (1e-9);

using P = pair<int, int>;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int h, w, m;
  cin >> h >> w >> m;
  vector<ll> nh(h, 0);   // i 行に置いてある対象物
  vector<ll> nw(w, 0);   // i 列に置いてある対象物

  set<P> t;  // 対象物が置いてある座標

  rep(i, m) {
    int hh, ww; cin >> hh >> ww; hh--; ww--;
    nh[hh]++;
    nw[ww]++;
    t.insert({hh, ww});
  }

  map<ll, vector<int>> mph, mpw;  // x 個破壊できる 行番号, 列番号

  rep(i, h) {
    int num = nh[i];
    mph[num].push_back(i);
  }
  rep(i, w) {
    int num = nw[i];
    mpw[num].push_back(i);
  }

  ll ans = 1;

/*
  cerr << "hmax: " << hmax << "   wmax: " << wmax << endl;

  dump(nh);
  dump(nw);

  dump(mph.rbegin()->second);
  dump(mpw.rbegin()->second);
*/

  auto itrx = mph.rbegin();

  for (auto& x : itrx->second) {
    // x: 爆弾を置く行番号
    auto itry = mpw.rbegin();
    for (auto& y : itry->second) {
      // y: 爆弾を置く列番号
      if (t.count({x, y}) == 0) {
        cout << itrx->first + itry->first << endl;
        return 0;
      } else {
        chmax(ans, ll(itrx->first + itry->first - 1));   // 交点に対象物がある
      }
    }
  }

  auto itry = mpw.rbegin();
  for (auto& y : itry->second) {
    // y: 爆弾を置く列番号
    auto itrx = mph.rbegin();
    for (auto& x : itrx->second) {
      // x: 爆弾を置く行番号
      if (t.count({x, y}) == 0) {
        cout << itrx->first + itry->first << endl;
        return 0;
      } else {
        chmax(ans, ll(itrx->first + itry->first - 1));   // 交点に対象物がある
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 26152
#include<bits/stdc++.h>
using namespace std;
int fun(int dp[], vector<int> adj[], int i){
    if(dp[i]!=-1) return dp[i];
    int ans=-1;
    for(auto itr:adj[i]){
        ans=max(ans,fun(dp,adj,itr)+1);
    }
    dp[i]=ans;
    return dp[i];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,a,b;
    cin>>n>>m;
    vector<int> adj[n+1],rev[n+1];
    for(int i=0;i<m;i++){
        cin>>a>>b;
        adj[a].push_back(b);
        rev[b].push_back(a);
        //cout<<a<<b;
    }
    int dp[n+1];
    memset(dp,-1,sizeof(dp));
   // vector<int> source;
    for(int i=1;i<=n;i++){
        if(adj[i].size()==0){
            //source.push_back(i);
            dp[i]=0;
    //        cout<<i<<endl;
        }
    }
    int ans=-1;
    for(int i=1;i<=n;i++){
        ans=max(ans,fun(dp,adj,i));
    }
    cout<<ans<<endl;
    // for(auto itr:source){
    //     for(auto itr2:rev[itr]){
            
    //     }
    // }
    
    
}

Measured memory_bytes: 14336
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

const int mx = 1e3 + 9;

int main() {
    set <ll> st;
    for (int i = 0; i < mx; i++) {
        ll x = i;
        x = x * x * x * x * x;
        st.insert(x);
        st.insert(-x);
    }

    ll X; scanf("%lld", &X);
    for (auto A5 : st) {
        ll B5 = A5 - X;
        auto it = st.find(B5);
        if (it == st.end()) continue;
        ll A = pow(abs(A5) * 1.0, 0.2);
        ll B = pow(abs(B5) * 1.0, 0.2);
        if (A5 < 0) A *= -1;
        if (B5 < 0) B *= -1;
        printf("%lld %lld\n", A, B);
        return 0;
    }

    // int i = 0;
    // for (auto it = st.begin(); i <= 100; i++, it++) {
    //     printf("%lld %lld\n", *it, (ll) pow(*it * 1.0, 0.2));
    // }
}

Measured memory_bytes: 4312