akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
 
public class Main {
    public static void main(String args[]){
        Scanner stdIn = new Scanner(System.in);
        
        int k = stdIn.nextInt();
        int n = stdIn.nextInt();
        
        int max = 0;
        int a[] = new int[n];
        
        for(int i = 0; i < n; i++){
            a[i] = stdIn.nextInt();
        }
        
        Arrays.sort(a);
        
        for(int i = 0; i < n - 1; i++){
            if(max < a[i + 1] - a[i]){
                max = a[i + 1] - a[i];
            }
        }
        
        int gyaku = a[0] + k - a[n - 1];
        //boolean flag = true;
        
        // for(int i = 0; i < s.length(); i++){
        //     a[i] = c[i] - 48;
        //     System.out.println(a[i]);
        // }
        //int sum = 0;
        //boolean flag = true;
        //for(int i = 0; i < s.length(); i++){
        //}
        
        System.out.println(Math.min(k - gyaku, k - max));
 
        //System.out.println();
        //System.out.print();
 
        stdIn.close();
    }
}


Measured memory_bytes: 77384
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;

using namespace std;


const long long MOD = 1000000007;

typedef class UnionFind {
private:
	int n;
	int* par;
	int* hight;
	int* group;

	int root(int a) {
		while (par[a] != a) a = par[a];
		return a;
	}
public:
	UnionFind(int num) {
		n = num;
		par = new int[n];
		hight = new int[n];
		group = new int[n];
		for (int i = 0; i < n; ++i) {
			par[i] = i;
			hight[i] = 1;
			group[i] = 1;
		}
	}
	~UnionFind() {
		delete[] par;
	}

	void unite(int a, int b) {
		int ra = root(a);
		int rb = root(b);
		if (ra == rb) return;

		if (hight[ra] > hight[rb]) {
			par[rb] = ra;
			group[ra] += group[rb];
		}
		else if (hight[ra] < hight[rb]) {
			par[ra] = rb;
			group[rb] += group[ra];
		}
		else {
			par[ra] = rb;
			++hight[rb];
			group[rb] += group[ra];
		}
	}
	bool same(int a, int b) {
		return root(a) == root(b);
	}

	int numofRoot() {
		int counter = 0;
		for (int i = 0; i < n; ++i) if (par[i] == i) ++counter;
		return counter;
	}

	int getgraoup(int i) {
		return group[root(i)];
	}
} Uf;

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

	int n, m, k;
	cin >> n >> m >> k;
	Uf uftree(n);
	int* ans;
	ans = new int[n];
	memset(ans, 0, sizeof(int)*n);
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		uftree.unite(a-1, b-1);
		--ans[a - 1];
		--ans[b - 1];
	}
	
	rep(i, n) ans[i] += uftree.getgraoup(i)-1;

	rep(i, k) {
		int c, d;
		cin >> c >> d;
		if (uftree.same(c - 1, d - 1)) {
			--ans[c - 1];
			--ans[d - 1];
		}
	}

	rep(i, n) {
		cout << ans[i] << " ";
	}

	cout << "\n";

	return 0;
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//long long ccw(const Point& A, const Point& B, const Point& C) {
//	return 1LL * (B.x - A.x)*(C.y - A.y) - 1LL * (B.y - A.y)*(C.x - A.x);
//}
string s;
int d[100001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> s;
	queue<int> L;
	stack<int> R;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'L') {
			L.push(i);
		}
		else {
			R.push(i);
		}
	}

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'R') {
			if (L.empty()) {
				d[s.size() - 1] += 1;
				continue;
			}
			int next = L.front();
			int len = next - i;
			if (len & 1) {
				d[next - 1] += 1;
			}
			else {
				d[next] += 1;
			}
		}
		else L.pop();
	}

	for (int i = s.size() - 1; i >= 0; i--) {
		if (s[i] == 'L') {
			if (R.empty()) {
				d[0] += 1;
				continue;
			}
			int next = R.top();
			int len = i - next;
			if (len & 1) {
				d[next + 1] += 1;
			}
			else {
				d[next] += 1;
			}
		}
		else R.pop();
	}

	for (int i = 0; i < s.size(); i++) {
		cout << d[i] << ' ';
	}cout << '\n';





}

Measured memory_bytes: 1360
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'[';
    for(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &i: a) out<<i<<',';
    out<<'}';
    return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

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

    while(1) {
        ll h, w;
        cin >> h >> w;
        if(!h) break;
        vector<vector<ll>> v(h, vector<ll>(w));
        REP(i, h) REP(j, w) cin >> v[i][j];

        ll ret = 0;
        REP(sx, w) REP(sy, h) FOR(gx, sx+2, w) FOR(gy, sy+2, h) {
            ll mi = LLINF;
            for(ll x=sx; x<=gx; ++x) {
                chmin(mi, v[sy][x]);
                chmin(mi, v[gy][x]);
            }
            for(ll y=sy; y<=gy; ++y) {
                chmin(mi, v[y][sx]);
                chmin(mi, v[y][gx]);
            }
            bool flag = true;
            ll sum = 0;
            for(ll y=sy+1; y<gy; ++y) for(ll x=sx+1; x<gx; ++x) {
                if(v[y][x] >= mi) flag = false;
                sum += mi - v[y][x];
            }

            if(flag) chmax(ret, sum);
        }
        cout << ret << endl;
    }

    return 0;
}



Measured memory_bytes: 3168
using System;

public class Problem_B
{
  public static void Main()
  {
    var N = int.Parse(Console.ReadLine());
    var a = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    Array.Sort(a);
    var dist = 0;
    for (var i = 0; i < N - 1; i++)
    {
      var next = a[i + 1];
      dist += next - a[i];
    }
    Console.WriteLine($"{dist}");
  }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
int a[51][27];
int ans[27];
#define inf 1000
int main(void)
{
    memset(a,0,sizeof(a));
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    string x;
    fill(ans,ans+26,inf);
    for(int i=0;i<n;i++)
    {
        cin>>x;
        for(int j=0;j<x.length();j++)
        {
            a[i][x[j]-'a']++;
        }
    }
    for(int i=0;i<26;i++)
    {
        for(int j=0;j<n;j++)
        {
            ans[i]=min(ans[i],a[j][i]);
        }
    }
    string res;
    for(int i=0;i<26;i++)
    {
        string z(ans[i],char('a'+i));
        res+=z;
    }
    cout << res <<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  // lcm
  ll A, B;
  cin >> A >> B;
  ll ans = A * B / __gcd(A, B);
  cout << ans << '\n';  
  return 0;
}

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

int main() {
  int n,t=0;
  string ans="Yes";
  cin >> n;
  vector<pair<int,int>> m(n,pair<int,int>());
  for(int i=0;i<n;i++) cin >> m.at(i).second >> m.at(i).first;
  sort(m.begin(),m.end());
  for(int i=0;i<n;i++) {
    t+=m.at(i).second;
    if(t>m.at(i).first) {
      ans="No";
      break;
    };
  };
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int X;cin>>X;
  
  if(X>=2000){
    cout<<1<<endl;
  }
  else{
    for(int i=0;i<21;i++){
      for(int j=0;j<20;j++){
        for(int k=0;k<20;k++){
          for(int l=0;l<20;l++){
            for(int m=0;m<20;m++){
              for(int n=0;n<20;n++){
  if(100*i+101*j+102*k+103*l+104*m+105*n==X){
    cout<<1<<endl;
    return 0;
  }
              }
            }
          }
        }
      }
    }
  
  cout<<0<<endl;
  }
}

Measured memory_bytes: 3612
def main():
    input = sys.stdin.readline
    try:
        n = int(input())
        a = list(map(int, input().split()))
        if len([i for i in a if i < 0]) % 2 == 0:
            print(sum((abs(i) for i in a)))
        else:
            arr = [abs(i) for i in a]
            print(sum(arr) - min(arr) * 2)
        
    finally:
        input = None

import sys; sys.setrecursionlimit(50000)
if __name__ == "__main__":
    main()


Measured memory_bytes: 15180
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD =  998244353;
const int  Inv2 = (MOD+1)/2;

     signed main(){
  int k;

  cin>>k;
k;
  int dp[11][10];
for(int i=0;i<10;i++)dp[0][i]=i+1;
for(int i=1;i<11;i++){
   dp[i][0]=dp[i-1][1];
   dp[i][1]=dp[i][0]+dp[i-1][2];
   for(int j=2;j<10;j++){dp[i][j]=dp[i][j-1]+dp[i-1][min(j+1,9ll)]-dp[i-1][j-2];}//cerr<<dp[i-1][j+1]-dp[i-1][j-2]<<' ';}
}
int ans[11];
ans[0]=dp[0][9]-dp[0][0];
for(int i=1;i<11;i++){ans[i]=ans[i-1]+dp[i][9]-dp[i][0];}//cerr<<ans[i]<<endl;}
int t=0,s=0,o;int l;
while(k>ans[s])s++;

   o=9;
  // cerr<<k<<' '<<ans[s]<<endl;
   if(s!=0)t=ans[s-1];
   else t=0;
   while(o!=0&&t+dp[s][o]-dp[s][0]>=k)o--;
   k-=(dp[s][o]-dp[s][0])+t;
   l=o+1;
     //cerr<<k<<' '<<ans[s]<<' '<<o+1<<' '<<s<<endl;
   s--;
while(s!=-1){
   o=l%10;o++;
   if(o-3>=0)t=dp[s][o-3];
   else t=0;
   if(o==10)o--;
   while(o!=-1&&k<=dp[s][o]-t)o--;
   l=l*10+o+1;
  // cerr<<k<<endl;
  if(o!=-1) k-=dp[s][o]-t;
s--;
}
cout<<l<<endl;
cout<<endl;



      
      
      }

        


Measured memory_bytes: 256
def main():
    n = int(input())
    a = n - 1
    b = 1
    menor = soma_digitos(a) + soma_digitos(b)
    temp = 0
    for i in range(n-2):
        a -= 1
        b += 1
        temp = soma_digitos(a) + soma_digitos(b)
        if menor > temp:
            menor = temp
    print(menor)

def soma_digitos(n):
    soma = 0
    while n >= 1:
        soma += n%10
        n = n//10
    return soma
main()

Measured memory_bytes: 3060
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
static const int INF = 2000000000;



int main(){
  string s;
  ll k;
  cin >> s >> k;
  if (s[0] == '1'){
    int c = 1;
    int no;
    for (int i = 1; i < s.size(); i++){
      if (s[i] == '1') c++;
      else {
        no = i;
        break;
      }
    }

    if (k <= no) {
      cout << 1 << endl;
      return 0;
    } else {
      cout << s[no] << endl;
    }
    
  } else {
    cout << s[0] << endl;
  }
}


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

int main() {
  int N, K;
  string S;
  cin >> N;
  cin >> S;
  cin >> K;
  for(int i= 0; i < N; i++) {
    if(S.at(i) != S.at(K-1)) {
      S.at(i) = '*';
    }
  }
  cout << S << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String line;
        // ????????\???
        while((line=br.readLine()) != null) {
            // ??????????????´??°?????????
            int time = Integer.parseInt(line);
            
            int hour = time / 3600;
            int minute = (time - (hour * 3600)) / 60;
            int second = time - (hour * 3600) - (minute * 60);
            
            System.out.println(hour + ":" + minute + ":" + second);
        }
    }
}

Measured memory_bytes: 24332
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <set>
const int inf=2147483647;
const int mo=924844033;	
const int N=4005;
using namespace std;
int n,m,tot;
bool lk[N];
long long f[N][N][2],jc[N],ans;
int main()
{
	//freopen("agc005d.in","r",stdin);
	//freopen("agc005d.out","w",stdout);
	scanf("%d%d",&n,&m);
	jc[0]=1;
	for(int i=1;i<=n;i++) jc[i]=1ll*jc[i-1]*i%mo;
	for(int i=1;i<=m;i++)
		for(int t=2;t--;)
			for(int j=i;j<=n;j+=m)
			{
				tot++;
				if(j!=i) lk[tot]=1;
			}
	f[0][0][0]=1;
	for(int i=0;i<n*2;i++)
		for(int j=0;j<=n;j++)
		{
			f[i+1][j][0]=(f[i][j][0]+f[i][j][1])%mo;
			if(lk[i+1]) f[i+1][j+1][1]=f[i][j][0];
		}
	for(int i=0,t=1;i<=n;i++,t=-t)
	{
		f[2*n][i][0]=1ll*(f[2*n][i][0]+f[2*n][i][1])*jc[n-i]%mo;
		ans=(ans+f[2*n][i][0]*t+mo)%mo;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 249472
#include<iostream>
#include<stdlib.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int main()
{
  int a[3][3];
  int check=1;
  int x1[8]={0,0,0,0,0,0,1,2};
  int x2[8]={0,0,0,1,2,2,0,0};
  int y1[8]={0,1,1,1,1,1,1,2};
  int y2[8]={1,0,1,1,2,1,1,1};
  int z1[8]={0,2,2,2,2,2,1,2};
  int z2[8]={2,0,2,1,2,0,2,2};
  
  for(int i=0;i<3;i++)
  {
    for(int j=0;j<3;j++)
    {
      cin>>a[i][j];
    }
  }
  
  int n;
  
  cin>>n;
  int b;
  
  for(int k=0;k<n;k++)
  {
    cin>>b;
    for(int l1=0;l1<3;l1++)
    {
      for(int l2=0;l2<3;l2++)
      {
        if(a[l1][l2]==b)
        {
          a[l1][l2]=0;
        }
      }
    }
  }
  
  for(int s=0;s<8;s++)
  {
    if(a[x1[s]][x2[s]]==0)
    {
      if(a[y1[s]][y2[s]]==0)
      {
        if(a[z1[s]][z2[s]]==0)
        {
          check=0;
        }
      }
    }     
  }
  
  if(check==0)
  {
    cout<<"Yes"<<endl;
  }
  else
  {
    cout<<"No"<<endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

void call(int n)
{
  int i = 0;
  
  while ( ++i <= n ) {

    int x = i;
    if ( x % 3 == 0 ){
        cout << " " << i;
        continue;
    }
    
    do {
        if ( x % 10 == 3 ){
            cout << " " << i;
            break;
        }
        x /= 10;
    } while ( x );
  }
  
  cout << endl;

}

int main() {
    
    int n = 0;
    cin >> n;
    call(n);
    return 0;

}



Measured memory_bytes: 3072
# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache

# 1整数
# n = int(input())

# 空白区切り2変数
from queue import Queue
from operator import mul
from functools import reduce
from queue import Queue
from operator import mul
from functools import reduce
from functools import lru_cache

input = sys.stdin.readline

# N個整数
#a, b, c = list(map(int, input().split()))

# 1整数
# n = int(input())

# 空白区切りリスト整数
# b = list(map(int, input().split()))

# 空白区切り文字列
# t, d = input().split()

ll = []
for i in range(5):
    ll.append(int(input()))

mm = 99999

kumi = list(itertools.permutations(ll))

for kk in kumi:
    sum = 0
    for s in kk:
        if sum % 10 != 0:
            sum += 10 - sum % 10
        sum += s
    mm = min(mm, sum)
print(mm)


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

int main(){
    int n,a,b;cin>>n>>a>>b;
    string s;cin>>s;

    int a_acc=0;
    int b_acc=0;

    for (int i=0;i<n;i++){
        auto c = s[i];
        if (c == 'c'){
            cout << "No" << endl;
        } else if (c == 'a'){
            if (a_acc + b_acc < a + b){
                a_acc++;
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        } else {
            if (a_acc + b_acc < a + b && b_acc < b){
                b_acc++;
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 896
# include <bits/stdc++.h>
using namespace std;
# define lli long long int
# define MOD 1000000007
# define INF 10000000000009
# define MAX 1000000


struct flowers{
    lli ht;
    lli bt;
};

void solve(){
    lli n;
    cin >> n;

    vector<flowers> v(n + 1);
    for(lli i = 1; i <= n; i++){
        cin >> v[i].ht;
    }
    for(lli i = 1; i <= n; i++){
        cin >> v[i].bt;
    }

    map<lli, lli> m;
    vector<lli> dp(n + 1);
    dp[1] = v[1].bt;
    m[v[1].ht] = dp[1];

    lli maxVal = dp[1];

    for(lli i = 2; i <= n; i++){
        auto it = m.upper_bound(v[i].ht);
        dp[i] = v[i].bt;
        if(it != m.begin()){
            it--;
            dp[i] += it->second;
        }

        m[v[i].ht] = dp[i];
        it = m.upper_bound(v[i].ht);
        while(it != m.end() and it->second <= dp[i]){
            auto tmp = it;
            tmp++;
            m.erase(it);
            it = tmp;
        }
        maxVal = max(maxVal, dp[i]);
    }
    cout << maxVal;
}

int main(){
    int t;
    t = 1;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 20236
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,n) for(long long i=0;i<n;++i)
#define REPP(i,m,n) for(long long i=m;i<n;++i)
#define rep(i,n) for(long long i = n-1;i>=0;--i)
#define repp(i,n,m) for(long long i = n-1; i >= m; --i)
#define ALL(N) (N.begin(),N.end())
#define de cout << "line : " << __LINE__ << " debug" << endl;
#define pb push_back
#define pq priority_queue
#define Dcout(N) cout << setprecision(20) << N << endl
constexpr long long MOD = 1000000007;
constexpr long long INF = 2147483647;
constexpr long long INFF = 9223372036854775807;

signed main() {
    cin.tie(0);
	ios::sync_with_stdio(false);
    int N;cin >> N;
    cout << N*N*N << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
int main(){
  ll N,D,x,y,i,ans = 0;scanf("%lld%lld",&N,&D);
  for(i=0;i<N;i++){
    scanf("%lld%lld",&x,&y);
    ans += x*x+y*y <= D*D;
  }
  printf("%lld\n",ans);
}

Measured memory_bytes: 3812
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define in(x, l, r) (ll)(l) <= (x) && (x) < (ll)(r)

int main() {
    int N;
    cin >> N;
    vector<int> L(N);
    rep(i,0,N) cin >> L[i];

    int ans = 0;
    rep(a,0,N-2) rep(b,a+1,N-1) rep(c,b+1,N) {
        if (L[a] == L[b]) continue;
        if (L[a] == L[c]) continue;
        if (L[c] == L[b]) continue;
        if (L[a] >= L[b] + L[c]) continue;
        if (L[b] >= L[a] + L[c]) continue;
        if (L[c] >= L[b] + L[a]) continue;
        ans++;
    }

    cout << ans << endl;
}

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

int main(void)
{
    ios_base::sync_with_stdio(0);   cin.tie(0);
    int n;
    cin >> n;
    int a[25], b[25], c[25];
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    for(int i = 1; i <= n - 1; ++i) cin >> c[i];
    int ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        ans += b[a[i]];
        if(i > 1 && a[i - 1] + 1 == a[i])   ans += c[a[i - 1]];
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int n; cin >> n;
    vector<int> p(n);
    int Max = 0;
    int ans = 0;
    rep(i,n) {
        cin >> p[i];
        ans += p[i];
        Max = max(Max, p[i]);
    }
    ans -= Max;
    ans += Max/2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
string s;
int sum[100010];
int main(){
    cin >> s;
    int n = s.size();
    int ans = (n/2)+1;
    for(int i=1;i<=n;i++){
        if(s[i-1]=='1') sum[i] = sum[i-1]+1;
        else sum[i] = sum[i-1];
    }
    for(;ans<=n;ans++){
        int tmp = sum[ans]-sum[n-ans];
        if(tmp==0 || tmp==(2*ans-n)) continue;
        else break;
    }
    printf("%d\n",ans-1);
    return 0;
}


Measured memory_bytes: 896
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
	int k,s,ans=0;
	cin>>k>>s;
	for(int x=0;x<=k;x++){
		for(int y=0;y<=k;y++){
			int z=s-x-y;
				if(0<=z && z<=k){
					ans++;
				}
		}
	}
	
	cout<<ans<<endl;
}


Measured memory_bytes: 256
//PanasonicD
import java.io.*;
import java.util.*;
public class Main{
static int t,n;
static int[] arr;
static StringBuilder ans=new StringBuilder();
public static void solve(char[] ch,int i,int c){
	//base case
	if(i==ch.length){
		System.out.println(new String(ch));
		return;
	}
	for(int x=0;x<=c;x++){
		ch[i]=(char)(x+'a');
		//we have placed maximum character
		if(ch[i]==(c+'a')){
			solve(ch,i+1,c+1);
		}
		else{
			solve(ch,i+1,c);
		}
	}
}
public static void main(String[] args) throws IOException{
		// BufferedReader br = new BufferedReader(new
  //      FileReader("sampleinp.txt"));
    	BufferedReader br = new BufferedReader( 
                             new InputStreamReader(System.in)); 
	 	
	 	n=Integer.parseInt(br.readLine());
	 	char[] ch=new char[n];
	 	solve(ch,0,0);
    }
}

Measured memory_bytes: 80012
#include<iostream>
using namespace std;
int main() {
	int n;
	int i = 0;
	int x = 0;;
	int a = 0, b = 0, c = 0;
	int f = 0;

	char s[100000];

	cin >> n >> s;
	while (1) {
		if (i >= n)break;
		if (s[i] != s[i + 1]&&s[i+1]!='\0') {
				x++;
				i++;
		}
		i++;
	}
	cout << x << endl;
}


Measured memory_bytes: 3212
n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)



Measured memory_bytes: 3500
package main

import "fmt"

func main() {
    var w, h, x, y, r int

    fmt.Scanf("%d %d %d %d %d", &w, &h, &x, &y, &r)

    if x-r >= 0 && y-r >= 0 && x+r <= w && y+r <= h {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}


Measured memory_bytes: 1152
import java.util.Scanner;
import java.util.Arrays;
import java.util.Set;
import java.util.HashSet;

public class Main{
  static int n, k;
  static int[] a;

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();
    k = sc.nextInt();
    a = new int[n];
    for(int i = 0; i < n; i++){
      a[i] = sc.nextInt();
    }

    Arrays.sort(a);

    if(a[n - 1] < k){
      System.out.println("IMPOSSIBLE");
      return;
    }

    if(n == 1){
      if(a[0] == k){
        System.out.println("POSSIBLE");
      }
      else{
        System.out.println("IMPOSSIBLE");
      }
      return;
    }

    for(int i = 0; i < n; i++){
      if(a[i] == k){
        System.out.println("POSSIBLE");
        return;
      }
    }

    for(int i = 0; i + 1 < n; i++){
      if(a[i + 1] - a[i] == 1){
        System.out.println("POSSIBLE");
        return;
      }
    }

    int diff = a[1] - a[0];
    boolean all = true;
    for(int i = 0; i + 1 < n; i++){
      if(a[i] == a[i + 1]){
        continue;
      }
      if(diff != a[i + 1] - a[i]){
        all = false;
        break;
      }
    }
    if(all){
      System.out.println("IMPOSSIBLE");
      return;
    }

    Set< Integer > diffs = new HashSet< >();
    for(int i = 0; i + 1 < n; i++){
      if(a[i + 1] == a[i]){
        continue;
      }
      diffs.add(a[i + 1] - a[i]);
    }

    for(Integer i : diffs){
      if(i != 0 && k % i == 0){
        System.out.println("POSSIBLE");
        return;
      }
    }

    System.out.println("IMPOSSIBLE");
  }
}

Measured memory_bytes: 50444
#include<stdio.h>

int main(){
		int n,i;
		char s[2][60];
		scanf("%d%s%s",&n,s[0],s[1]);
		long long ans=3,mod=1000000007;
		if(s[0][0]==s[0][1])ans=6;
		for(i=1;i<n;i++){
				if(s[0][i]==s[0][i-1])continue;
				if(s[0][i-1]==s[1][i-1])ans*=2;
				else if(s[0][i]!=s[1][i])ans*=3;
				ans%=mod;
		}
		printf("%lld\n",ans);
		return 0;
}


Measured memory_bytes: 128
n = int(input())
l = list(map(int,input().split()))
s = 1
f = 1
x = 1000000000000000000
l.sort()
if l[0]==0:
  print(0)
elif l[0]==1 and l[-1]==1:
  print(1)
else:
  l = l[::-1]
  for i in l:
      s *= i
      if s>x:
          print(-1)
          f = 0
          break
  if f==1:
    print(s)

Measured memory_bytes: 21788
#include <iostream>
#include <algorithm>
#include <string>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

int main() {
  std::string s, t;
  cin >> s;
  cin >> t;

  std::sort(s.begin(), s.end());
  std::sort(t.rbegin(), t.rend());
  
  if (s < t) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}

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

int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    sort(arr,arr+n);
    int sum=0;
    for( int i = n-1; i >= 1; i--){ 
        int l = 0, r = i-1; 
        while( l < r){ 
            if( arr[l] + arr[r] > arr[i]){ 
                sum += r - l ;  
                r--;   
            } 
            else 
                l++;   
        } 
    } 
    cout<<sum<<endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(a) sort(a.begin(), a.end())
const int INF = 1<<30;
const ll MOD = 1000000007;

int main(void) {

    int s, w; cin >> s >> w;
    if (s <= w) cout << "unsafe" << endl;
    else cout << "safe" << endl;


    return 0;
}

Measured memory_bytes: 3636
using System;
using System.Linq;

namespace CF2016qC
{
    class B
    {
        static void Main(string[] args)
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int K = input[0];
            int T = input[1];

            int[] a = Console.ReadLine().Split().Select(int.Parse).OrderByDescending(x => x).ToArray();

            int max = a[0];

            for (int i = 1; i < T; i++)
            {
                max -= a[i];
                if (max <= 0) { Console.WriteLine(0); return; }
            }

            Console.WriteLine(max - 1);
        }
    }
}


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

int main()
{
   string s;
   cin>>s;
   for(int i=0;i<s.size();i++)
   {
       if(s[i]=='1')s[i]='9';
       else if(s[i]=='9')s[i]='1';
   }
   cout<<s<<endl;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var X int
	fmt.Scan(&X)

	ans := 1
	for i := 1; i <= X; i++ {
		for j := 2; j < X; j++ {
			v := int(math.Pow(float64(i), float64(j)))
			if v <= X && ans < v {
				ans = v
			}
			if X < v {
				break
			}
		}
	}
	fmt.Println(ans)
}


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

int main(){
  int A,B;
  cin>>A>>B;
  string S;
  cin>>S;
  int cnt=0;
  for(int i=0;i<A;i++){
    if(S[i]>='0'&&S[i]<='9') cnt++;
  }
  if(S[A]=='-') cnt++;
  for(int i=A+1;i<=A+B;i++){
    if(S[i]>='0'&&S[i]<='9') cnt++;
  }
  if(cnt==(A+B+1)) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
  return 0;
  
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
	static int mod = (int) 1e9 + 7;
	static int DX[] = { -1, 0, 1, 0 }, DY[] = { 0, -1, 0, 1 };
	
	static int n;
	static long k;
	static long a[];
	public static void main(String[] args) {
		FastScanner fs = new FastScanner(System.in);
		n = fs.nextInt();
		k = fs.nextLong();
		a = fs.nextLongArray(n);
		Arrays.sort(a);
		long INF = (long)(1e18)+1;
		long l = -INF;
		long r = INF;
		while(l+1<r) {
			long c = (l+r)/2;
			if(check(c))l=c;
			else r = c;
		}
		System.out.println(l);
	}
	//x未満の組合せがk個未満ならtrue
	static boolean check(long x) {
		long tot = 0;
		for(int i=0;i<n;i++) {
			long now = a[i];
			int l = -1, r = n;
			if(now >= 0) {
				while(l+1<r) {
					int c = (l+r)/2;
					if(now * a[c] < x) l = c;
					else r = c;
				}
				tot += (l+1);
			}
			else {
				while(l+1<r) {
					int c = (l+r)/2;
					if(now * a[c] < x) r = c;
					else l = c;
				}
				tot += (n - r);
			}
			if((long)a[i] * a[i]<x)tot--;
		}
		if(tot/2 < k) return true;
		else return false;
	}
}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScanner(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}

Measured memory_bytes: 48884
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
  
#define SENTINEL (1000000001)
#define putChar(c) ; *p = (char)(c); ++p;
  
int c = 0;
int S[500000];
int L[250001];
int R[250001];
char str[5500010];
char *p = str;
  
int getNum(void) {
    int n = 0;
    while ((*p >= '0') && (*p <= '9')) {
        n = n * 10 + (int)(*p - '0');
        ++p;
    }
    ++p;
    return n;
}
  
void putNum(int n) {
    int d;
    if (n < 10) {
        putChar( '0' + n );
        return;
    }
    d = n / 10;
    if (d) putNum(d);
    putChar( '0' + (n % 10) );
}
  
void Merge(int A[], int left, int mid, int right) {
    int i = 0, j = 0, k = left;
    int n1 = mid - left;
    int n2 = right - mid;
    //L[]??¨R[]??????????????????
    memcpy(L, A + left, n1 * sizeof(int));
    memcpy(R, A + mid, n2 * sizeof(int));
    L[n1] = R[n2] = SENTINEL;
    for (; k < right; ++k) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            ++i;
        } else {
            A[k] = R[j];
            ++j;
        }
    }
}
  
void MergeSort(int A[], int left, int right) {
    int mid;
    if (left + 1 < right) {
        mid = (left + right) >> 1;
        MergeSort(A, left, mid);
        MergeSort(A, mid, right);
        Merge(A, left, mid, right);
        c += right - left;
    }
}
  
int main(void) {
    register int i;
    int n;
      
    fread(str, 1, 5500000, stdin);
    n = getNum();
    for (i = 0; i < n; ++i) {
        S[i] = getNum();
    }
      
    MergeSort(S, 0, n);
      
    --n;
    p = str;
    for (i = 0; i < n; ++i) {
        putNum(S[i]);
        putChar( ' ' );
    }
    putNum(S[i]);
    putChar( '\n' );
      
    putNum(c);
    putChar( '\0' );
      
    puts(str);
  
    return 0;
}

Measured memory_bytes: 9216
#include <iostream>
#include <cstdio>

using namespace std;
int a[10],x;
char c;

int main(){
    while(cin>>c&&c!='\0'){
        if(c=='0') a[x++]=0;
        else if(c=='1') a[x++]=1;
        else{
            if(x)
                x--;
        }
    }
    if(x){
        for(int i=0;i<x;i++)
            printf("%d",a[i]);
        printf("\n"); 
    }
    return 0;
}

Measured memory_bytes: 256
package main

import (
  "bufio"
  "fmt"
  "os"
  "sort"
  "strconv"
  "strings"
)

func main() {
  input := Input{bufio.NewReaderSize(os.Stdin,1000000)}
  n,k,q := input.NextInts()
  a := append(input.NextIntArray(),-1)
  m := 1000000001
  for i:=0;i<n+1;i++ {
    var s []int
    for x,y:=-1,0;y<n+1;y++ {
      if a[y] < a[i] {
        if y-x-1 >= k {
          var b []int
          for j:=x+1;j<y;j++ { b = append(b,a[j]) }
          sort.Ints(b)
          for j:=0;j<y-x-k;j++ { s = append(s,b[j]) }
        }
        x = y
      }
    }
    sort.Ints(s)
    if len(s) >= q && m > s[q-1]-a[i] { m = s[q-1]-a[i] }
  }
  fmt.Println(m)
}

type Input struct {
  reader *bufio.Reader
}
func(i *Input) NextLine() string {
  var buffer []byte
  for {
    line,isPrefix,err := i.reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func(i *Input) NextInts() (int,int,int) {
  s := strings.Split(i.NextLine()," ")
  x,_ := strconv.Atoi(s[0])
  y,_ := strconv.Atoi(s[1])
  z,_ := strconv.Atoi(s[2])
  return x,y,z
}
func(i *Input) NextIntArray() []int {
  s := strings.Split(i.NextLine()," ")
  a := make([]int,len(s))
  for i:=0;i<len(s);i++ { a[i],_ = strconv.Atoi(s[i]) }
  return a
}

Measured memory_bytes: 8832
#include <bits/stdc++.h>
#include <string>
#include <cmath>
#include <sstream>
//#include <unordered_map>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORD(i, a, b) for(int i = (a-1); i >= (b); i--)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
typedef long long int ll;
using namespace std;
ll mod=1000000007;
//ll mod=67280421310721;
//ll mod=998244353;
ll INF=1e18;
ll po(ll a,ll b)
{
	ll re=1;
	while(b)
	{
		if(b%2==1)
		{
			re=(re*a);
			re%=mod;
		}
		a=(a*a);
		a%=mod;
		b>>=1;
	}
	return re;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int test=1;
//	cin>>test;
	while(test--)
	{
		string s;
		cin>>s;
		int n=s.size();
		int ans=0;
		FORD(i,n,0)
		{
			if(s[i]=='5')
			{
				ans+=5;
				if(i!=0)
				{
					if(s[i-1]>='5')
					s[i-1]=(s[i-1]+1);
				}
			}
			else if(s[i]<'5')
			{
				ans+=(s[i]-'0');
			}
			else
			{
				ans+=(('9'-s[i])+1);
				if(i==0)
				ans++;
				else
				s[i-1]=(s[i-1]+1);
			}
		}
		cout<<ans;
	}
	return 0;
}


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

int main(){

    int n;
    cin >> n;

    for(int i=0;i*4<=n;i++){
        for(int j=0;i*4+j*7<=n;j++){
            if(n==i*4+j*7){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
 
#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
 
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
 
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
 
#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
 
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
 
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
 
    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };
 
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
 
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}


fn main() {
    input! {
        x: usize,
        y: usize,
        z: usize,
        k: usize,
        mut a: [u64; x],
        mut b: [u64; y],
        mut c: [u64; z],
    }

    a.sort_by(|a, b| b.cmp(a));
    b.sort_by(|a, b| b.cmp(a));
    c.sort_by(|a, b| b.cmp(a));

    let mut v = Vec::new();

    for i in a.iter() {
        for j in b.iter() {
            v.push(i+j);
        }
    }

    v.sort_by(|a, b| b.cmp(a));

    let mut ans = Vec::new();
    for i in v.iter().take(3000) {
        for j in c.iter() {
            ans.push(i+j);
        }
    }

    ans.sort_by(|a, b| b.cmp(a));

    for a in ans.iter().take(k) {
        println!("{}", a);
    }
    
}




Measured memory_bytes: 44276
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstdio>
using namespace std;

#define int long long
#define INF 1e18

signed main() {
    int n; cin >> n;
    vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end(), greater<int>());

    int alice = 0;
    int bob = 0;
    for(int i = 0; i < n; i++) {
        if(i % 2 == 0) alice += a[i];
        else bob += a[i];
    }

    int ans = alice - bob;
    cout << ans << endl;
}


Measured memory_bytes: 256
// DP(???????¨??????? Dynamic Programing)
// ????????±???????????¢???
// ?????£??????????????°???
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A

#include <iostream>
using namespace std;

#define MAX_N 44

struct memo{
    int num;
    bool flg;
}Memo[MAX_N+1];

int n;
int fib(int);

int main()
{
    cin >> n;
    for(int i=0;i<MAX_N+1;++i)
        Memo[i].flg=false;
    cout << fib(n) << endl;
    return 0;
}

int fib(int m){
    if(m == 0){
        if(!Memo[0].flg){
        Memo[0].num=1;
        Memo[0].flg=true;
        }
        return 1;
    }
    if(m == 1){
        if(!Memo[1].flg){
        Memo[1].num=2;
        Memo[1].flg=true;
        }
        return 1;
    }

    if(Memo[m].flg){
        return Memo[m].num;
    }
    else{
        Memo[m].num=fib(m-1) + fib(m-2);
        Memo[m].flg=true;
        return fib(m-1) + fib(m-2);
    }
}

Measured memory_bytes: 1160
#include <iostream>

int main()
{
    std::ios_base::sync_with_stdio(false);
    int D, N, ans = 1;
    std::cin >> D >> N;
    while (D--)
        ans *= 100;
    if (N == 100)
        ++N;
    std::cout << ans * N << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int n,m,cnt,inf=1e9,q[5010],tot;
ll ans,f[5010],g[5010],mo=1e9+7,jc[5010],ny[5010];
bool flag;
ll pw(ll i,ll k)
{
	ll a=1;
	while(k)
	{
		if(k&1)a*=i,a%=mo;
		i*=i;i%=mo;
		k>>=1;
	}
	return a;
}
ll cc(ll a,ll b)
{
	if(a<b)return 0;
	return jc[a]*ny[b]%mo*ny[a-b]%mo;
}
ll aa(ll a,ll b)
{
	if(a<b)return 0;
	return jc[a]*ny[a-b]%mo;
}
void add(ll &a,ll b)
{
	a+=b;
	if(a>=mo)a-=mo;
}
struct graph
{
	int x1[5010],r[10010],vt[10010],su[10010],mx,cen;
	void adde(int a,int b)
	{
		r[++cnt]=x1[a];x1[a]=cnt;vt[cnt]=b;
		r[++cnt]=x1[b];x1[b]=cnt;vt[cnt]=a;
	}
	void dfs(int i,int fa)
	{
		int s,a,b,j,k;
		a=x1[i];su[i]=1;
		k=0;
		while(a)
		{
			b=vt[a];
			if(b!=fa)
			{
				dfs(b,i);
				su[i]+=su[b];
				if(su[b]>k)k=su[b];
			}
			a=r[a];
		}
		if(n-su[i]>k)k=n-su[i];
		if(su[i]*2==n)flag=1;
		if(k<mx)mx=k,cen=i;
	}
	void solve()
	{
		int i,s,a,b,j,k;
		a=x1[cen];
		while(a)
		{
			b=vt[a];
			if(su[b]<su[cen])q[++tot]=su[b];
			a=r[a];
		}
		if(cen!=1)q[++tot]=n-su[cen];
		//cout<<"tot "<<tot<<endl;
		//for(i=1;i<=tot;i++)cout<<" "<<q[i];cout<<endl;
		f[0]=1;ans=jc[n];
		for(i=1;i<=tot;i++)
		{	
			for(s=0;s<=n;s++)
				for(k=1;k<=q[i];k++)
					if(s+k<=n)add(g[s+k],f[s]*cc(q[i],k)%mo*aa(q[i],k)%mo);
			for(s=0;s<=n;s++)add(f[s],g[s]),g[s]=0;	
		}
		for(i=1;i<=n;i++)
		{
			//cout<<"f "<<i<<" "<<f[i]<<endl;
			if(i&1)add(ans,mo-(f[i]*jc[n-i]%mo));
			else add(ans,f[i]*jc[n-i]%mo);
		}
		printf("%lld",ans);
	}
}gr;
int main()
{
	int i,s,a,b,j,k;
	jc[0]=ny[0]=1;for(i=1;i<=5000;i++)jc[i]=jc[i-1]*i%mo,ny[i]=pw(jc[i],mo-2);
	scanf("%d",&n);
	for(i=1;i<n;i++)scanf("%d%d",&a,&b),gr.adde(a,b);
	gr.mx=inf;gr.cen=0;gr.dfs(1,0);
	if(flag){printf("%lld",jc[n/2]*jc[n/2]%mo);return 0;}
	//cout<<"sb "<<gr.cen<<endl;
	gr.solve();
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;
typedef long long ll;

using reverse_priority_queue = priority_queue<ll, vector<ll>, std::greater<ll>>;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(3 * n);
    for(int i = 0; i < 3 * n; ++i){
        cin >> a.at(i);
    }

    vector<ll> lmax(3 * n, 0);
    {
        reverse_priority_queue qsum;
        ll total = 0;
        for(int i = 0; i < 3 * n; ++i){
            if(qsum.size() < n){
                total += a.at(i);
                qsum.push(a.at(i));
            }else if(qsum.top() < a.at(i)){
                ll tmp = qsum.top();
                qsum.pop();
                qsum.push(a.at(i));
                total += a.at(i) - tmp;
            }
            lmax.at(i) = total;
        }
    }

    vector<ll> rmin(3 * n, 0);
    {
        priority_queue<ll> qsum;
        ll total = 0;
        for(int i = 3 * n - 1; i >= 0; --i){
            if(qsum.size() < n){
                total += a.at(i);
                qsum.push(a.at(i));
            }else if(qsum.top() > a.at(i)){
                    ll tmp = qsum.top();
                    qsum.pop();
                    qsum.push(a.at(i));
                    total += a.at(i) - tmp;
            }
            rmin.at(i) = total;
        }
    }

    ll ans = numeric_limits<ll>::min();
    for(int i = n - 1; i < 2 * n; ++i){
        ans = max(ans, lmax.at(i) - rmin.at(i + 1));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9068
import sys
import numpy as np
import copy
import math
import time

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func()
    inp_str = input_raw.strip().split()
    N = int(inp_str[0])
    input_raw = read_func()
    inp_str = input_raw.strip().split()
    odd_count = 0
    for i in range(N):
        if int(inp_str[i])%2 != 0:
            odd_count += 1
    if odd_count % 2 == 0:
        print "YES"
    else:
        print "NO"


if __name__ == '__main__':
    main()

Measured memory_bytes: 30184
#include "iostream"
#include "list"
#include "vector"
#define int long long
using namespace std;

void set_max(int &x, list<int> args)
{
	for (auto i : args)
	{
		x = max(x, i);
	}
}

signed main()
{
	int n, w;
	cin >> n >> w;
	vector<int> weight(n + 1), value(n + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> weight[i] >> value[i];
	}
	vector<vector<int>> dp(w + 1, vector<int>(n + 1, 0));
	for (int i = 0; i <= w; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			set_max(dp[i][j], {dp[i][j - 1]});
			if (weight[j] <= i)
			{
				set_max(dp[i][j], {dp[i - weight[j]][j - 1] + value[j]});
			}
		}
	}
	cout << dp[w][n] << endl;
}


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

using namespace std;

#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define int long long
#define mp make_pair
#define ff first
#define ss second
#define pii pair<int,int>
#define INF LLONG_MAX
#define EPS 1e-9
#define all(v) (v).begin(),(v).end()
#define sq(x) ((x)*(x))
#define foreach(it, v) for(auto it=(v).begin(); it != (v).end(); ++it)
#define tr(...) cout<<__FUNCTION__<<' '<<__LINE__<<" = ";trace(#__VA_ARGS__, __VA_ARGS__)


#define tr(...) cout<<__FUNCTION__<<' '<<__LINE__<<" = ";trace(#__VA_ARGS__, __VA_ARGS__)

template<typename T>
void trace(const char* name, T&& arg1){cout<<name<<" : "<<arg1<<endl;}
 
template<typename T, typename... Args>
void trace(const char* names, T&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma-names)<<" : "<<arg1<<" | ";trace(comma+1,args...);}
 
typedef long double dbl;
bool codejam = 0;

const int MOD = 1000*1000*1000 + 7;
const int NMAX = 1000*1000 + 11;

int arr[NMAX];
int n,m,p,q,k,a,b,c,ans;
string s,str;
char ch;
vector<int> v;

void solve()
{
    cin>>str;
    if(str[1] == 'R') cout<<"ABC";
    else
        cout<<"ARC";
    return;
}

int32_t main(){ fio;
    int t = 1;
    int cs = 1;
    // cin>>t;
    while(t--){
        if(codejam){
            cout<<"Case #"<<cs<<": ";
        }
        cs++;
        solve();
        cout<<"\n";
    }
}

Measured memory_bytes: 3652
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
  int n, m;
  cin >> n >> m;
  cout << (n - 1) * (m - 1) << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

#define MAX_N 100000007

long long par[MAX_N];
long long ranka[MAX_N];


void init(long long n)
{
	for(long long i=0;i<n;i++)
	{
		par[i]=i;
		ranka[i]=0;
	}
}

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

void unite(long long x,long long y)
{
	x=find(x);
	y=find(y);
	if(x==y)return;

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

bool same(long long x,long long y)
{
	return find(x)==find(y);
}

int main()
{
	int n;
	cin >> n;
	vector<pair<int,int>> x(n),y(n);
	for(int i=0;i<n;i++)
	{
		int xx,yy;
		cin >> xx >> yy;
		x[i]=make_pair(xx,i);
		y[i]=make_pair(yy,i);
	}
	sort(x.begin(),x.end());
	sort(y.begin(),y.end());
	vector<pair<int,pair<int,int>>> dist;

	for(int i=1;i<n;i++)
	{
		dist.push_back(make_pair(x[i].first-x[i-1].first,make_pair(x[i].second,x[i-1].second)));
	}
	for(int i=1;i<n;i++)
	{
		dist.push_back(make_pair(y[i].first-y[i-1].first,make_pair(y[i].second,y[i-1].second)));
	}
	sort(dist.begin(),dist.end());
	int ans=0;
	init(n);
	for(int i=0;i<dist.size();i++)
	{
		auto now=dist[i];
		int cost=now.first;
		int a=now.second.first;
		int b=now.second.second;
		if(same(a,b))continue;
		ans+=cost;
		unite(a,b);
	}
	cout << ans << endl;
}

Measured memory_bytes: 7536
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

long n, ans = 0;
vector<long> a;
vector<long> b;

void func(long x, long y)
{
    if (a[x] < b[y]) {
        ans += a[x];
        b[y] -= a[x];
        a[x] = 0;
    } else {
        ans += b[y];
        a[x] -= b[y];
        b[y] = 0;
    }
}



int main()
{
    cin >> n;
    a.resize(n+1);
    b.resize(n);

    for (long i = 0; i < n+1; ++i) cin >> a[i];
    for (long i = 0; i < n; ++i) cin >> b[i];

    for (long i = 0; i < n; ++i) {
        func(i, i);
        if (b[i] > 0) func(i+1, i);
    }

    printf("%ld\n", ans);

    return 0;
}

Measured memory_bytes: 1792