akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		String s = sc.next();
		String t = sc.next();
		
		// 計算
		int result = 100000;
		for(int i = 0; i < s.length()-t.length()+1; i++){
		    int tmp = 0;
		    for(int j = 0; j < t.length(); j++){
		        if(s.charAt(i+j) != t.charAt(j)) tmp++;
		    }
		    result = min(result, tmp);
		}
		
		
		// 出力
		System.out.println(result);
	}
	
	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}


Measured memory_bytes: 25868
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)

N = int(readline())
G = [[] for i in range(N)]

for i in range(N - 1):
  x,y = map(int,readline().split())
  G[x - 1].append(y - 1)
  G[y - 1].append(x - 1)

DIV = 10 ** 9 + 7

# 頂点iが白であるときの場合の数は、(iの子の白である場合 + 黒である場合)の数同士の積
# 頂点iが黒であるときの場合の数は、iの子が白である場合の数同士の積
# 自分の子が決まっていない場合は再帰的に探索する

# dp[i][j] = 頂点iがj(1:黒, 0:白)である場合の数
dp = [[-1] * 2 for i in range(N)]

def search_black(X, parent): # Xが黒の場合の数を求める
  if dp[X][1] != -1:
    return dp[X][1]
  # 自分に子供がいなければ、1を返す
  children = G[X]
  if len(children) == 1 and children[0] == parent:
    dp[X][1] = 1
    return 1
  ans = 1
  for child in children:
    if child == parent:
      continue
    ans *= search_white(child, X)
    ans %= DIV
  dp[X][1] = ans
  return ans
  
def search_white(X, parent): # Xが白の場合の数を求める
  if dp[X][0] != -1:
    return dp[X][0]
  # 自分に子供がいなければ、1を返す
  children = G[X]
  if len(children) == 1 and children[0] == parent:
    dp[X][0] = 1
    return 1
  ans = 1
  for child in children:
    if child == parent:
      continue
    ans *= (search_white(child, X) + search_black(child, X))
    ans %= DIV
  dp[X][0] = ans
  return ans
  
print((search_white(0, -1) + search_black(0, -1)) % DIV)


Measured memory_bytes: 113576
import java.io.InputStream;
import java.util.NoSuchElementException;
public class Main {
	public static void main(String[] args)throws Exception{
		int N=nextInt();
		int K=nextInt();
		int A[]=new int[N];
		int L[]=new int[N];
		int R[]=new int[N];
		boolean ans=true;
		for(int i=0;i<N;i++){
			A[i]=nextInt();
			if(i-A[i]<=0)
				L[0]++;
			else{
				L[i-A[i]]++;
				ans=false;
			}
			if(i+A[i]>=N-1)
				R[N-1]++;
			else{
				R[i+A[i]]++;
				ans=false;
			}
		}
		for(int j=0;j<K;j++){
			int cout=0,key=0;
			if(ans==false){
				for(int i=0;i<N;i++){
					key+=L[i];
					A[i]=key+cout;
					cout++;
					key--;
					cout-=R[i];
				}
				ans=true;
				R=new int[N];
				L=new int[N];
				for(int i=0;i<N;i++){
					if(i-A[i]<=0)
						L[0]++;
					else{
						L[i-A[i]]++;
						ans=false;
					}
					if(i+A[i]>=N-1)
						R[N-1]++;
					else{
						R[i+A[i]]++;
						ans=false;
					}
				}
			}
			else{
				for(int i=0;i<N;i++){
					System.out.println(N);
				}
				System.exit(0);
			}
		}
		for(int i=0;i<N;i++){
			System.out.println(A[i]);
		}
	}
	//FastScanner
	static InputStream in = System.in;
	static  byte[] buffer = new byte[1024];
	static int length = 0, p = 0;
	public static boolean hasNextByte () {
		if (p < length) return true;
		else {
			p = 0;
			try {length = in.read(buffer);}
			catch (Exception e) {e.printStackTrace();}
			if (length == 0) return false;
		}
		return true;
	}
	public static int readByte () {
		if (hasNextByte() == true) return buffer[p++];
		return -1;
	}
	public static boolean isPrintable (int n) {return 33<=n&&n<=126;}
	public static void skip () {
		while (hasNextByte() && !isPrintable(buffer[p])) p++;
	}
	public static boolean hasNext () {skip(); return hasNextByte();}
	public static String next () {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int temp = readByte();
		while (isPrintable(temp)) {
			sb.appendCodePoint(temp);
			temp = readByte();
		}
		return sb.toString();
	}
	public static int nextInt () {return Math.toIntExact(nextLong());}
	public static int[] nextInts (int n) {
		int[] ar = new int[n];
		for (int i=0; i<n; i++) ar[i] = nextInt();
		return ar;
	}
	public static long nextLong () {
		if (!hasNext()) throw new NoSuchElementException();
		boolean minus = false;
		int temp = readByte();
		if (temp == '-') {
			minus = true;
			temp = readByte();
		}
		if (temp<'0' || '9'<temp) throw new NumberFormatException();
		long n = 0;
		while (isPrintable(temp)) {
			if ('0'<=temp && temp<='9') {
				n *= 10;
				n += temp - '0';
			}
			temp = readByte();
		}
		return minus? -n : n;
	}
}


Measured memory_bytes: 57168
# # -*- coding: utf-8 -*-

#
N, X, Y = map(int, input().split(' '))
edges = [(i, i+1) for i in range(N-1)]
graph = [{} for _ in range(N)]
for src, dst in edges:
    graph[src][dst] = 1
    graph[dst][src] = 1
graph[X-1][Y-1] = 1
graph[Y-1][X-1] = 1

import collections
d_frq_dict = collections.Counter()
for start in range(N):
    dist = [float('inf') for _ in range(N)]
    dist[start] = 0
    buf = [start]
    while buf:
        src = buf.pop(0)
        for dst in graph[src]:
            if dist[dst] == float('inf'):
                dist[dst] = dist[src] + 1
                buf.append(dst)

    d_frq_dict.update(dist)
    # print(dist)

for d in range(1, N):
    print(d_frq_dict[d]//2)


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

int main() {
  int N;
  cin >> N;
  vector<long> A(N + 1), B(N + 1);
  A.at(1) = B.at(1) = 1;
  long ans = 0, cnt = 0;
  for (int i = 2; i <= N; i++) {
    for (int j = i; j > 1; j--) {
      ans += j * B.at(i / j), cnt += B.at(i / j);
    }
    A.at(i) = ans + (B.at(i) = i * i * i - cnt);
    ans = cnt = 0;
  }
  cout << A.at(N) << "\n";
}

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

using namespace std;

#define ll long long
#define vi  vector<int>
#define vvi vector<vi>
#define pi  pair<int,int>
#define mp  make_pair
#define pb  push_back
#define MOD 1e9 + 7
#define PAI  3.1415
#define all(x) (x).begin(),(x).end()
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define pr(x) cout << x << endl
#define Endl endl
#define rep(i,n) for(int i = 0 ; i < n; i++)

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int ddx[8] = {-1,0,1,-1,1,-1,0,1};
const int ddy[8] = {-1,-1,-1,0,0,1,1,1};
const int inf = 99999999;
const ll linf = 1LL << 62;

ll gcd(ll a,ll b){
  if(a < b)swap(a , b);
  if(a % b == 0) return b;
  else gcd(b, a%b);
}

ll lcm(ll a,ll b){
  if(a < b)swap(a , b);
  return (a/gcd(a , b))*b;
}

int main(){

  int n,m;
  cin >> n >> m;

  int a[1000],b[1000],c[1000],dist[100][100] = {0};

  for(int i = 0 ; i < m ; i++){
    cin >> a[i] >> b[i] >> c[i];
    a[i]--; b[i]--;
  }

  rep(i,n){
    rep(j,n){
       if(i != j)dist[i][j] = inf;
    }
  }

  rep(i,m){
    dist[a[i]][b[i]] = min(dist[a[i]][b[i]] , c[i]);
    dist[b[i]][a[i]] = min(dist[b[i]][a[i]] , c[i]);
  }

  rep(k,n){
    rep(i,n){
      rep(j,n){
        dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
      }
    }
  }

  int ans = m;
  rep(i,m){
    bool flag = false;
    rep(j,n) if(dist[j][a[i]]+c[i] == dist[j][b[i]])flag = true;
    if(flag) ans--;
  }

  pr(ans);

  return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//template<typename key, typename val>
//using ordered_tree =
//  tree<key, val, greater<>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int64;
typedef complex<double> comp;
const double pi = 3.14159265358979323846;
const int inf = (int)1e+9 + 2;
const int64 inf64 = (int64)1e+18 + 2;
const double dinf = 1e+20;
const int mod = 1'000'000'007;//998244353;
const int base = 2187;
const double eps = 1e-8;
const int N = 200'001;
const int LOGN = 19;

int n, m, k;

void solve(int test)
{
  cin >> n;
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i].first;
    a[i].second = i + 1;
  }
  sort(begin(a), end(a));
  for (auto& pr : a) {
    cout << pr.second << ' ';
  }
  cout << '\n';
}

void precalc()
{
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  precalc();
  int test = 1;
  //cin >> test;
  //auto start = chrono::high_resolution_clock::now();
  for (int i = 1; i <= test; ++i)
    solve(i);
  //cerr << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << '\n';
  return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <algorithm>
using namespace std;
int N, K; long long ret;
int main() {
	cin >> N >> K;
	for (int i = K + 1; i <= N; i++) {
		ret += 1LL * (N / i) * (i - K) + max(N % i - K + 1, 0);
	}
	cout << ret - (K == 0 ? N : 0) << endl;
	return 0;
}

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

int main(){
  int sx,sy,tx,ty;
  cin>>sx>>sy>>tx>>ty;

  int dx=tx-sx;
  int dy=ty-sy;

  for(int i=0;i<dy;i++){
    cout<<"U";
  }

  for(int i=0;i<dx;i++){
    cout<<"R";
  }

  for(int i=0;i<dy;i++){
    cout<<"D";
  }

  for(int i=0;i<dx+1;i++){
    cout<<"L";
  }

  for(int i=0;i<dy+1;i++){
    cout<<"U";
  }

  for(int i=0;i<dx+1;i++){
    cout<<"R";
  }

  cout<<"D";
  cout<<"R";

  for(int i=0;i<dy+1;i++){
    cout<<"D";
  }

  for(int i=0;i<dx+1;i++){
    cout<<"L";
  }

  cout<<"U"<<endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
// 普通にやったら大変そう 気をつくって, それに対してクエリは耐えられないので前処理をしておく必要がある. 
// 1からたどって, 子供をvectorに追加,  N * Nの更新に耐えられない. 
// セグメント木が必要?
// どうやら累積和らしい.
// 累積していけば問題ないよね. 
// 1番から初めてたどっていくのか
// 親

void dfs(int i, vector<int>& v, vector<int>* G, vector<bool>& checked) {
  for (auto a : G[i]) {
    if (checked[a]) continue;
    checked[a] = true;
    v[a] += v[i];
    dfs(a, v, G, checked);
  }
}

signed main() { 
  int N , Q;
  cin >> N >> Q;
  vector<int> G[N];
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<int> v(N, 0);
  for (int i = 0; i < Q; i++) {
    int q, x;
    cin >> q >> x;
    q--;
    v[q] += x;
  }
  vector<bool> checked(N, false);
  checked[0] = true;
  dfs(0, v, G, checked);
  for (int i = 0; i < N; i++) {
    cout << v[i] << " ";
  }
  cout << endl;
}

Measured memory_bytes: 30592
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main() {
    int a1,a2,a3; cin >> a1 >> a2 >> a3;
    cout << max(a1, max(a2, a3)) - min(a1, min(a2, a3));
}

Measured memory_bytes: 256
A,B,K = map(int,input().split())
if B-A+1 <= 2*K:
  for i in range(A,B+1):
    print(i)
else:
  for i in range(A,A+K):
    print(i)
  for i in range(B-K+1,B+1):
    print(i)

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

using namespace std;

int main() {
  char c;
  cin >> c;

  bool vowel = false;

  for (int i = 0; i < 5; i++) {
    if ("aiueo"s.at(i) == c) {
      cout << "vowel" << endl;
      vowel = true;
    }
  }
  if (vowel == false) {
    cout << "consonant" << endl;
  }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;
using Graph = vector<vector<int>>;

long long N, M, K;
long long FC[100002] = {0};
int POS[100002] = {0};

void dfs(Graph &GF, map<int, int> &m, int a, int pos){
	if(m.count(a) != 0) return;
	m[a] = 1;
	POS[a] = pos;
	for(auto next_a : GF[a]){
		dfs(GF, m, next_a, pos);
	}
}

long long calcFC(Graph &GF, Graph &GB, map<int, int> &m, int a, int doDFS, int pos){
	if(FC[a] != -1) return FC[a];
	if(GF[a].size() == 0){
		FC[a] = 0;
		return 0;
	}

	if(doDFS == 1){
		dfs(GF, m, a, pos);
	}
	int f = 0; //直接友人
	for(int i=0; i<GF[a].size(); i++){
		if(m.count(GF[a][i]) != 0){
			f++;
		}
	}
	int b = 0; //ブロック
	for(int i=0; i<GB[a].size(); i++){
		if(m.count(GB[a][i]) != 0){
			b++;
		}
	}
	FC[a] = m.size() - f - b - 1; //自分を抜く
	return FC[a];
}

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M >> K;
	Graph GF(N); 
	Graph GB(N);
	for(int i=0; i<N; i++){ FC[i] = -1; }

	for(int i=0; i<M; i++){
		int a, b;
		cin >> a >> b;
		GF[a - 1].push_back(b - 1);
		GF[b - 1].push_back(a - 1);
	}
	for(int i=0; i<K; i++){
		int c, d;
		cin >> c >> d;
		GB[c - 1].push_back(d - 1);
		GB[d - 1].push_back(c - 1);
	}


	vector<map<int, int>> v;
	for(int i=0; i<N; i++){
		int found = 0; int j;
		if(POS[i] != 0){
			calcFC(GF, GB, v[POS[i]], i, 0, 0);
		}
		else{
			map<int, int> m;
			calcFC(GF, GB, m, i, 1, v.size());
			v.push_back(m);
		}
		printf("%lld ", FC[i]);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 29408
s = input()

if s[0]=='A':
    t = 'a'+s[1:]
    for i in range(2,len(s)-1):
        if s[i]=='C':
            n = i
            u = 'a'+s[1:n]+'c'+s[n+1:]
            if u==s.lower():
                print('AC')
                exit()
print('WA')

Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

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

  vector<long long> A(m);

  for (long long i = 0; i < m; i++) {
    long long a;
    cin >> a;
    A[i] = a;
  }

  long long sum = accumulate(A.begin(), A.end(), 0);

  long long rest = n - sum;
  
  cout << ((rest >= 0) ? rest : -1) << endl;
  return 0;
}


Measured memory_bytes: 3268
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();

		// 直接
		if (Math.abs(a - c) <= d){
			System.out.println("Yes");
			return;
		}
		// 間接
		if (Math.abs(a - b) > d){
			System.out.println("No");
			return;
		}
		if (Math.abs(b - c) > d){
			System.out.println("No");
			return;
		}
		System.out.println("Yes");
	}
}

Measured memory_bytes: 22740
#include <bits/stdc++.h>
//#include "atcoder/all"
typedef long long int ll;
using namespace std;
// using namespace atcoder;
int main() {
    int n;
    cin >> n;
    int count = 0;
    bool ok = false;
    for (int i = 0; i < n; i++) {
        int d1, d2;
        cin >> d1 >> d2;
        if (d1 == d2) {
            count++;
        }
        else {
            count = 0;
        }
        if (count == 3) {
            ok = true;
        }
    }
    if (ok) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <stdlib.h>
using namespace std;

int main(){
	int x, a, b;
	cin >> x >> a >> b;
	if (abs(a - x) > abs(b - x))
	{
		cout << 'B' << endl;
	}else if (abs(a - x) < abs(b - x))
	{
		cout << 'A' << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define ll long long
#define mp make_pair
using namespace std;
int main(){
	string s;
	cin>>s;
	ll bc=0,wc=0,res=0;
	for(int i=s.size()-1;i>=0;i--){
		if(s[i]=='W'){
			wc++;
		}
		if(s[i]=='B'){
			res+=wc;
		}
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	long long int n,m,k;
	m=0;
	cin>>n;
	for(long long int i=1;i<n;i++)
    {
        k=0;
        if(n%i)
            k=n/i;
        else
            k=n/i-1;
        if(!k)break;
        else m+=k;
    }
    cout<<m<<endl;
	return 0;
}


Measured memory_bytes: 3636
N = int(input())
mod = 10**9 + 7

dp = [[[[0 for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N+1)]
dp[0][3][3][3] = 1
let = {i:l for i,l in enumerate('AGCT')}

for i in range(1,N+1):
    for l3 in range(4):
        for l2 in range(4):
            for l1 in range(4):
                for nextl in range(4):
                    flag = True
                    for j in range(4):
                        lets = list(let[l3]+let[l2]+let[l1]+let[nextl])
                        if j >= 1:
                            lets[j-1],lets[j] = lets[j],lets[j-1]
                        if 'AGC' in ''.join(lets):
                            flag = False
                            break
                    if flag:
                        dp[i][l2][l1][nextl] += dp[i-1][l3][l2][l1]
                        dp[i][l2][l1][nextl] %= mod
ans = 0
for l3 in range(4):
    for l2 in range(4):
        for l1 in range(4):
            ans = (ans + dp[N][l3][l2][l1])%mod
print(ans)


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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define ALL(x) x.begin(),x.end()
#define PB push_back
#define LL long long

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {
    _for(i,0,v.size()) os << v[i] << " ";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){
    for(typename set<T>::iterator it = v.begin();it != v.end();it++)
    os << *it <<" ";
    return os;
}

struct lines{
    int l,r;
    lines(int l,int r):l(l),r(r){;}
    bool operator<(const lines &b){
        return l < b.l;
    }
};

const int maxn = 2e5+5;
int A[maxn];
int C[maxn];
vector<lines> vl;
vector<int> alpha[26];
string s;

int lowbit(int x){return x&(-x);}

void add(int a,int v){
    for(int i = a; i < maxn;i += lowbit(i)){
        C[i] += v;
    }
}
LL sum(int a){
    LL ret = 0;
    for(int i = a;i > 0;i-=lowbit(i)){
        ret += C[i];
    }
    return ret;
}

LL rev_p(int sz){
    LL ret = 0;
    _rep(i,1,sz){
        ret += sum(A[i]-1);
        //cout <<ret<<endl;
        add(A[i],1);
    }
    return ret;
}

int main()
{
    cin >> s;
    int sz = s.size();

    _for(i,0,sz){
        int d = s[i] - 'a';
        alpha[d].push_back(i);
    }
    int odd = 0;
    _for(i,0,26){
        int szi = alpha[i].size();
        if(szi % 2){
            odd++;
            _rep(j,0,szi/2){
                vl.push_back(lines(alpha[i][j]+1,alpha[i][szi-1-j]+1));
            }
        }
        else{
            _for(j,0,szi/2){
                vl.push_back(lines(alpha[i][j]+1,alpha[i][szi-1-j]+1));
            }
        }
    }
    if(odd >= 2){
            cout << -1 <<endl;
            return 0;
    }

    sort(ALL(vl));
    int cnt = 1;
    int rev = sz;
    _for(i,0,vl.size()){
        lines &ll = vl[i];
        if(ll.l != ll.r){
            A[ll.l] = cnt++;
            A[ll.r] = rev--;
        }
        else A[ll.l] = (sz/2+1);
    }

    reverse(A+1,A+sz+1);

    //_for(i,1,4) cout << A[i] << endl;

    cout << rev_p(sz) << endl;

    return 0;
}

Measured memory_bytes: 4600
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	#P,Q,R = map(int, input().split(" "))
	N = int(input())
	#S = input()
	#S = list(S)
	W = list(map(int, input().split(" ")))

	#W.sort()

	ans = -1
	for i in range(1, N):
		#tmp = bisect_left(W, i)
		grp1 = W[:i]
		grp2 = W[i:]

		#print(grp1)
		#print(grp2)

		if ans == -1 or ans > abs(abs(sum(grp1)) - abs(sum(grp2))):
			ans = abs(abs(sum(grp1)) - abs(sum(grp2)))


	print(ans)


	

if __name__ == "__main__":
	main()

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


#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

void pre(){


}

void solve(){


}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
	int n;cin>>n;
	vi v(n);
	rep(i,n) cin>>v[i];
	sort(all(v));
	if(n%3==0){
		if(v[0]==v[n/3-1]&&v[n/3]==v[2*n/3-1]&&v[2*n/3]==v[n-1]&&(v[0]^v[n/3]^v[2*n/3])==0){
			cout<<"Yes";
		}
		else cout<<"No";
	}
	else {
		if(v[0]==v[n-1]) cout<<"Yes";
		else cout<<"No";
	}

	return 0;
}



Measured memory_bytes: 640
from collections import deque

N = int(input())
H = W = 4
S = 1 << 16
P = [list(map(int, input().split())) for i in range(N)]
C = [input() for i in range(H)]
I = "RGB".index
ps = set()
for i in range(N):
    h, w = P[i]
    for y in range(1-h, H):
        py = max(0, y); sh = min(H, y+h) - py
        for x in range(1-w, W):
            px = max(0, x); sw = min(W, x+w) - px
            ps.add((px, py, sw, sh))
L = len(ps)
M = [0]*L; V = [None]*L
for l, (x, y, w, h) in enumerate(ps):
    s = S-1; b = 0
    v = [0]*3
    for i in range(h):
        for j in range(w):
            k = 1 << ((y+i)*W + x+j)
            s ^= k
            c = I(C[y+i][x+j])
            v[c] |= k
    M[l] = s
    V[l] = v

U = [-1]*S
que = deque([0])
U[0] = 0
while que:
    state = que.popleft()
    d = U[state]
    for i in range(L):
        n_state = state & M[i]
        for v in V[i]:
            if not v:
                continue
            if U[n_state | v] != -1:
                continue
            U[n_state | v] = d+1
            que.append(n_state | v)
print(U[S-1])


Measured memory_bytes: 7724
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<(int)(n); i++)
#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)
using namespace std;

int main() {
  int K; cin >>K;
  string S; cin >>S;

  string Ans = "";
  if ( K<S.size() ) {
    Ans = S.substr( 0, K )+"...";
  } else Ans = S;
  cout <<Ans <<endl;;
}


Measured memory_bytes: 3580
car = []
while 1:
    try:
        i = int(input())
        if  i == 0:
            print(car.pop()) 
        else:
            car.append(i)
    except ValueError:
        print(car)
        for j in range(len(car)):
            print(car.pop())
        break
    except EOFError:
        break


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

int main() {
  string s;
  cin >> s;
  rep(i, s.size()-8) cout << s[i];
  cout << endl;
  return 0;
}

Measured memory_bytes: 3532
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <intrin.h>

using namespace std;

typedef long long ll;

vector <vector<int>> g;
vector<int> otv;
vector<int> used;

void bfs() {
	queue<pair<int, int>> q;
	q.push({ 0, -1 });
	used[0] = 1;

	while (q.size()) {
		pair<int, int> v = q.front();
		q.pop();

		otv[v.first] = v.second;

		for (int to : g[v.first]) {
			if (!used[to]) {
				q.push({ to, v.first });
				used[to] = 1;
			}
		}
	}
}

inline void solve() {
	int n, m;
	cin >> n >> m;
	g.resize(n);
	otv.resize(n, -1);
	used.resize(n, 0);

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	bfs();

	bool ok = 1;
	for (int i = 1; i < n; i++) {
		if (otv[i] == -1)
			ok = 0;
	}

	if (ok) {
		cout << "Yes\n";
		for (int i = 1; i < n; i++)
			cout << otv[i] + 1 << '\n';
	}
	else
		cout << "No";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int q = 1;
	//cin >> q;
	for (; q > 0; q--) {
		solve();
		cout << '\n';
	}
}

Measured memory_bytes: 10852
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define cool ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
#define MAX 1000001
#define mod 1000000007
#define pie 3.14159265358979323846
void solve()
{
	int n,k,i,j,x,y,f=0,m;
	cin>>n>>m;
	int arr[n+1]={0};
	vector<int> v;
	vector<int> ve[n+1];
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		ve[x].push_back(y);
		ve[y].push_back(x);
		if(x==1&&arr[y]==0){
			v.push_back(y);
			arr[y]=1;
		}
		if(y==1&&arr[x]==0){
			v.push_back(x);
			arr[x]=1;
		}
	}
	for(i=0;i<v.size();i++){
		for(j=0;j<ve[v[i]].size();j++){
			if(arr[ve[v[i]][j]]==0&&ve[v[i]][j]!=1){
				arr[ve[v[i]][j]]=v[i];
				v.push_back(ve[v[i]][j]);
			}
		}
	}
	for(i=2;i<=n;i++){
		if(arr[i]==0){
			f=1;
			break;
		}
	}
	if(f==1)
	cout<<"No\n";
	else{
		cout<<"Yes\n";
		for(i=2;i<=n;i++) cout<<arr[i]<<"\n";
	}
}
int main()
{ 
    cool;
    int t;
    //cin>>t;
    t=1;
    while(t--){
    	solve();
	}
    return 0;
}


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

typedef long long ll;
typedef pair<int,int> P;

int main(){
        int n,r,table[50],work[50];
        while(cin>>n>>r&&n,r){
                for(int i=0;i<n;i++)table[i]=n-i;
                int p,c;
                for(int i=0;i<r;i++){
                        cin>>p>>c;
                        for(int k=0;k<c;k++)work[k]=table[p-1+k];
                        for(int k=0;k<p-1;k++)work[c+k]=table[k];
                        for(int k=p+c-1;k<n;k++)work[k]=table[k];
                        for(int k=0;k<n;k++)table[k]=work[k];
                }
                cout<<table[0]<<endl;
        }
        return 0;
}



Measured memory_bytes: 3068
n = int(input())
p = list(map(int, input().split()))
plen = len(p)
num = 0
for i in range(plen):

    if i == 0 or i == plen-1:
        continue
    ls = [p[i-1], p[i], p[i+1]]
    max_ = ls.index(max(ls))
    min_ = ls.index(min(ls))
    if max_ != 1 and min_ != 1:
        num += 1
print(num)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define fi first
#define se second
const int maxn=1e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int trans(char c)
{
	return c-'0';
}
bool check(int x)
{
	if(x<=12&&x>=1) return true;
	else return false;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	string a;
	cin>>a;
	int x=0,y=0;
	x=trans(a[0])*10+trans(a[1]);
	y=trans(a[2])*10+trans(a[3]);
	if(check(x)&&check(y)) cout<<"AMBIGUOUS"<<'\n';
	else if(check(x)) cout<<"MMYY"<<'\n';
	else if(check(y)) cout<<"YYMM"<<'\n';
	else cout<<"NA"<<'\n';
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb           push_back
#define pf           push_front
#define in           insert
#define ff           first
#define ss           second
#define mp           make_pair
#define int          long long
#define uint         unsigned long long
#define rep(i,x,m)   for(int i=x;i<m;i++)
#define repr(i,x,m)  for(int i=x;i>=m;i--)
#define MOD          1000000007
#define endl         "\n"
#define all(v)       v.begin(),v.end()
#define rall(v)      v.rbegin(),v.rend()
#define vi           vector<int>
#define vs           vector<string>
#define pi           pair<int,int>
#define di           deque<int>
#define sz(x)       (int)x.size()
#define pq           priority_queue<int>
#define pqs          priority_queue<int,vi,greater<int> >
#define fix(y)       fixed<<setprecision(y)
#define print(v)     for(int i=0;i<v.size();i++) cout<<v[i]<<" ";cout<<endl
#define noob         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

int fac[2000005]={0};
void factorial(){ fac[0]=1; fac[1]=1; for(int i=2;i<200005;i++) fac[i]=((i%MOD)*(fac[i-1]%MOD))%MOD;}
int power(int n,int m)
{int p=1;if(m==0)return 1;p=(power(n,m/2)%MOD);p=(p%MOD*p%MOD)%MOD;
return(m&1?((p%MOD*n%MOD)%MOD):(p%MOD));}
int ncr(int n,int r){return ((fac[n]*power(fac[r],MOD-2))%MOD*power(fac[n-r],MOD-2))%MOD;}

void ram5564()
{
    int n;
    cin>>n;
    if(n%1000==0)

    {
        cout<<0;return;
    }
    cout<<1000-(n%1000);
}

signed main()
{
        noob
        // #ifndef ONLINE_JUDGE
        //  freopen("input.txt","r",stdin);
        //  freopen("output.txt","w",stdout);
        //  #endif   
        
        int t=1;
        //cin>>t;
        while(t--)
        ram5564();
        return 0;
}

Measured memory_bytes: 3652
w, h, n = map(int, input().split())
xl = w
xs = 0
yl = h
ys = 0
for i in range(n):
    x, y, a = map(int, input().split())
    if a == 1:
        xs = max(xs, x)
    elif a == 2:
        xl = min(xl, x)
    elif a == 3:
        ys = max(ys, y)
    elif a == 4:
        yl = min(yl, y)
if (yl <= ys) or (xl <= xs):
    print(0)
else:
    print((yl-ys)*(xl-xs))

Measured memory_bytes: 3064
def dfs(v,t,f,used,graph):
    if v==t:
        return f
    used[v] = True
    for to in graph[v]:
        c = graph[v][to]
        if used[to] or c==0:
            continue
        d = dfs(to,t,min(f,c),used,graph)
        if d>0:
            graph[v][to] -= d
            graph[to][v] += d
            return d
    return 0
 
def max_flow(s,t,graph):
    flow = 0
    while True:
        used = [False]*len(graph)
        f = dfs(s,t,float('inf'),used,graph)
        flow += f
        if f==0 or f==float('inf'):
            return flow
 
H,W = map(int,input().split())

a = [input() for _ in range(H)]
a = [[s for s in a[i]] for i in range(H)]

graph = [{} for _ in range(H+W+2)]

for h in range(H):
    for w in range(W):
        if a[h][w]=='o':
            graph[h][H+w] = 1
            graph[H+w][h] = 1
        if a[h][w]=='S':
            graph[H+W][h] = float('inf')
            graph[H+W][H+w] = float('inf')
            graph[h][H+W] = 0
            graph[H+w][H+W] = 0
        if a[h][w]=='T':
            graph[H+W+1][h] = 0
            graph[H+W+1][H+w] = 0
            graph[h][H+W+1] = float('inf')
            graph[H+w][H+W+1] = float('inf')

ans = max_flow(H+W,H+W+1,graph)
if ans == float('inf'):
    ans = -1

print(ans)

Measured memory_bytes: 47068
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority_queue
#include<deque>//double_ended queue
using namespace std;
typedef pair<int,int> P;//Pでpair<-,->を表す。
typedef long long LL; 

int main()
{ 
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        int m;
        m=s[i]-'A';
        s[i]='A'+(m+n)%26;
    }
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

//#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

const int MAX_N = 3e4+10;
int dp[MAX_N][10][10][10];

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);

    int N; cin >> N;
    string S; cin >> S;
    map<int,int> mp;
    multiset<int> s1,s2;
    set<string> se;

    REP(i,N){
        s2.insert(S[i]-'0');
    }
    REP(i,N){
        dump(S[i])
        s2.erase(s2.find(S[i]-'0'));
        REP(j,10){
            if(s1.find(j) == s1.end()) continue;
            REP(k,10){
                if(s2.find(k) == s2.end()) continue;

                string tmp;
                dump(j)
                dump(k)
                tmp += to_string(j)+S[i]+to_string(k);
                dump(tmp)
                se.insert(tmp);
            }
        }
        s1.insert(S[i]-'0');
    }
    int ans = 0;
    for(auto t : se){
        dump(t)
        ans++;
    }
    cout << ans << endl;



}


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

class Main {
  int N, M, ans;
  List<List<Integer>> adj;
  int[] dp;
  Main(int n, int m, List<List<Integer>> a) {
    N = n; M = m; adj = a;
    ans = 0;
    dp = new int[N];
    Arrays.fill(dp, -1);
  }

  void solve() {

    for (int i = 0; i < N; i++) {
      if (dp[i] == -1) dp[i] = dp(i);
    }

    for (int i = 0; i < N; i++) {
      //System.out.print(dp[i] + " ");
      ans = Math.max(ans, dp[i]);
    }
    //System.out.println();
  }

  int dp(int cur) {
    if (dp[cur] != -1) return dp[cur];
    dp[cur] = 0;
    for (int i : adj.get(cur)) {
      dp[cur] = Math.max(dp[cur], dp(i) + 1);
    }
    return dp[cur];
  }

  

  public static void main(String[] args) {
    Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    int N = in.nextInt();
    int M = in.nextInt();
    List<List<Integer>> adj = new ArrayList<>(N);
    for (int i = 0; i < N; i++) {adj.add(new ArrayList<>());}
    for (int i = 0; i < M; i++) {
      int u = in.nextInt() - 1;
      int v = in.nextInt() - 1;
      adj.get(u).add(v);
    }
    Main test = new Main(N, M, adj);
    test.solve();
    System.out.println(test.ans);
  }

}

Measured memory_bytes: 105020
#include <bits/stdc++.h>
#define MAX 1000001
//#define EZPZ_LEMON_SQUEEZY
using namespace std;
vector<int> M[MAX];
int n, e, q;
bool vis[MAX];
int color[MAX];
void dfs(int index, int cor)
{
	vis[index] = 1;
	color[index] = cor;
	for (int i = 0; i < M[index].size(); i++) {
		if (!vis[M[index][i]]) {
			dfs(M[index][i], cor);
		}
	}
}

int main()
{
#ifdef EZPZ_LEMON_SQUEEZY
	freopen("D:\\out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	int s, t;
	cin >> n >> e;
	for (int i = 0; i < e; i++) {
		cin >> s >> t;
		M[s].push_back(t);
		M[t].push_back(s);
	}
	memset(vis, 0, sizeof(vis));
	memset(color, 0, sizeof(color));
	int c = 1;
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			dfs(i, c);
			c++;
		}
	}

	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> s >> t;
		if (color[s] == color[t] && color[s] != 0) cout << "yes" << endl;
		else cout << "no" << endl;
	}
	return 0;
}



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

char q(char z,int x){
  char Z=z;  
  while(x>0){
    Z+=1; x-=1;
    if(Z>'z'){Z-=26;}
  }
  return Z;
}
 
int main() {
  string s;
  cin >> s;
  int K;
  cin >> K;
  int S=s.size();
  for(int i=0;i<S;i++){
    if(i==S-1){s[i]=q(s[i],K%26);}
    else if(s[i]=='a'){continue;}
    else if('z'-s[i]+1<=K){
      K-='z'-s[i]+1; s[i]='a';
    }
    else{continue;}
  }
  cout << s << endl;
}

Measured memory_bytes: 512
while 1:
    a=int(input())
    if a==0:break
    a=[a]+[int(input()) for _ in range(4)]
    r=a.count(1);s=a.count(2);p=5-r-s
    if [r,s,p].count(0)==1:
        if r and s:w=1
        elif r and p:w=3
        else:w=2
        [print([2,1][w==x])for x in a]
    else:print('3\n'*5,end='')

Measured memory_bytes: 7672
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s; cin>>s;
  bool a=false,b=false,c=false;
  for(int i=0; i<3; i++){
    if(s.at(i)=='a')
      a=true;
    else if(s.at(i)=='b')
      b=true;
    else if(s.at(i)=='c')
      c=true;
  }
  if(a and b and c)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <sstream> 
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl "\n"
#define CPrint(c)  for(auto i:(c)) { cout<<i<<" "; } nl 
#define eb   emplace_back
#define ef   emplace_front
#define pb   push_back
#define pf   push_front
#define popb pop_back
#define popf pop_front
#define mp   make_pair
//debuggers
#define trace2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define trace3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define trace4(w,x,y,z) cout<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
typedef long long ll;
const int INF=1e9+5;
using namespace std;

int main()
{
	FAST_IO;
	int n;
	cin >> n;
	vector<int> h(n);
	for(int i=0;i<n;i++)
	{
		cin >> h[i];
	}
	vector<int> dp(n,INF);//stores cost incurred to reach n
	dp[0] = 0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<=i+2;j++)
		{
			dp[j] = min(dp[j],dp[i]+abs(h[j]-h[i]));
		}
	}
	cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<iostream>
using std::max;

int main()
{
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	printf("%lld",max(a * 1ll * d,max(a * 1ll * c,max(b * 1ll * d,b * 1ll * c))));
	return 0;
}

Measured memory_bytes: 3748
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijo(ll x){
  ll z=1;
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i <=n;i++){
    num*=yakusu[i];
  }
  return num;
}



int main(){
  ll N,M;cin>>N>>M;
  vl a(N);vl b(M);vl c(M);
  vector<pair<ll,ll>> p(M);
  rep(i,N){
    cin>>a[i];
  }
  rep(i,M){
    cin>>b[i]>>c[i];
    p[i]= make_pair(c[i],b[i]);
  }
  sort(all(a));
  sort(all(p));
  reverse(all(p));
  int j=0;
  ll ans =0;
  rep(i,M){
    int k=0;
    while(p[i].second>k&&j<N){
      a[j] =max(a[j],p[i].first);
      j++;
      k++;
      
    }
    
  }
  rep(i,N)ans+=a[i];
  cout<<ans<<endl;
  
}

Measured memory_bytes: 4224
import collections
N = int(input())
S=[]
for i in range(N):
    S.append(input())
c = collections.Counter(S)
print('AC x {}'.format(c['AC']))
print('WA x {}'.format(c['WA']))
print('TLE x {}'.format(c['TLE']))
print('RE x {}'.format(c['RE']))


Measured memory_bytes: 16620
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
double pi=3.1415926535897932384626433832;
typedef pair<int,int>pii;
int main()
{
	int sx,sy,gx,gy;
	scanf("%d%d%d%d",&sx,&sy,&gx,&gy);
	int num;
	scanf("%d",&num);
	vector<pii>vec;
	for(int i=0;i<num;i++)
	{
		int za,zb;
		scanf("%d%d",&za,&zb);
		if(sx>gx)za=-za;
		if(sy>gy)zb=-zb;
		vec.push_back(make_pair(za,zb));
	}
	if(sx>gx)sx=-sx,gx=-gx;
	if(sy>gy)sy=-sy,gy=-gy;
	sort(vec.begin(),vec.end());
	vector<int>zv;
	for(int i=0;i<num;i++)if(sx<=vec[i].first&&vec[i].first<=gx&&sy<=vec[i].second&&vec[i].second<=gy)zv.push_back(vec[i].second);
	vector<int>now;
	for(int i=0;i<zv.size();i++)
	{
		int low=lower_bound(now.begin(),now.end(),zv[i])-now.begin();
		if(low==now.size())now.push_back(zv[i]);
		else now[low]=zv[i];
	}
	double ans=100.0*(gx-sx+gy-sy);
	ans-=(20.0-5.0*pi)*now.size();
	if(now.size()==min(gx-sx,gy-sy)+1)ans+=5.0*pi;
	printf("%.20lf\n",ans);
}

Measured memory_bytes: 4336
#include <inttypes.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

uint64_t get_gcd(uint64_t a, uint64_t b)
{
    if (b == 0)
        return a;
    else
        return get_gcd(b, a % b);
}

int main(int argc, char const* argv[])
{
    int64_t N, X, x[(int)1e5];
    int64_t gcd, d[(int)1e5];

    scanf("%" PRId64 "%" PRId64, &N, &X);
    for (int i = 0; i < N; i++) {
        scanf("%" PRId64, &x[i]);
        d[i] = llabs(x[i] - X);
    }

    gcd = d[0];
    for (int i = 1; i < N; i++) {
        gcd = get_gcd(gcd, d[i]);
    }

    printf("%" PRId64 "\n", gcd);
}


Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
import numpy as np

# input
N = int(input())
s = []
for _ in range(N):
    s.append( input() )

# Step.1
count = 0
for string in s:
    count += string.count("AB")

# Step.2
s_ba, s_oa, s_bo = [], [], []
## sort
for string in s:
    if string[0] == "B":
        if string[-1:] == "A": 
            s_ba.append(string)
        else:
            s_bo.append(string)
    elif string[-1:] == "A":
        s_oa.append(string)

#print(s_oa)
#print(s_ba)
#print(s_bo)

## solve
element = 0
if len(s_oa) != 0: 
    s_oa.pop(0)
    element += 1

element += len(s_ba)

if len(s_bo) != 0: 
    s_bo.pop(0)
    element += 1

element += min(len(s_bo), len(s_oa))

if element != 0:
    count += element - 1

print(count)


Measured memory_bytes: 21644
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
int main(){
    int n;cin>>n;
    vector<int> p(n);
    vector<int> q(n);
    rep(i,n)cin>>p[i];
    rep(i,n)cin>>q[i];
    
    vector<int> a(n);
    rep(i,n)a[i]=i+1;
    map<vector<int>,int> mp;
    do{
        mp[a]=mp.size();
    }while(next_permutation(all(a)));
    int ans=abs(mp[p]-mp[q]);
    cout<<ans<<endl;
}

Measured memory_bytes: 5248
/*
	submission # - User: herp_sy
	https://atcoder.jp/contests/
*/

import java.util.*;
import java.util.Collections; // sorting use
import java.io.*;
import static java.lang.System.*;

public class Main{
	public static void main(String[] args){
		int n;
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> a = new ArrayList<Integer>();
		ArrayList<Integer> b = new ArrayList<Integer>();

		n = sc.nextInt();
		a = new ArrayList<Integer>();
		b = new ArrayList<Integer>();

		for(int i = 0; i < n; ++i){
			a.add(sc.nextInt());
			b.add(a.get(i));
		}
		Collections.sort(b);
		Collections.reverse(b);
		for(int i = 0; i < n; ++i){
			if(a.get(i) == b.get(0)){
				out.println(b.get(1));
			}
			else{
				out.println(b.get(0));
			}
		}
	}
}


Measured memory_bytes: 97428
#include<iostream>
using namespace std;
long N,X,M;
int vis[1<<17];
long pre[1<<17];
main()
{
	cin>>N>>X>>M;
	for(int i=0;i<M;i++)vis[i]=-1;
	long ans=0;
	int tu=0;
	while(N>0)
	{
		if(vis[X]>=0)
		{
			int be=tu-vis[X];
			ans+=(ans-pre[X])*(N/be);
			N%=be;
		}
		if(N>0)
		{
			vis[X]=tu++;
			pre[X]=ans;
			ans+=X;
			N--;
			X=X*X%M;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 4784
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_10_D
#include <iostream>
#include <cstdio>
#include <cmath>

const double inf = 100;

using namespace std;
int main(){
  int n;
  cin >> n;
  double x[n],y[n];
  for(int i =0; i<n;i++){
    cin >> x[i];
  }
  for(int i =0; i<n;i++){
    cin >> y[i];
  }

  double in;
  for(int i = 1; i<5; i++){
    double sum = 0;
    double distance = 0;
    if(i == 4){
      int max = abs(x[0] - y[0]);
      for(int j=0;j<n;j++){
        if(max < abs(x[j]-y[j])) max = abs(x[j]-y[j]);
      }
      distance = pow(max, inf);
      distance = pow(distance, 1.0/inf);
      }
    else{
      for(int j=0;j<n;j++){
        sum += pow(abs(x[j]- y[j]), i);
        }
      in = 1/double(i);
      distance = pow(sum, in);
      }
    printf("%.6lf\n", distance);
    }
}

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

int main(){
    long long  n, a, b, c, d, e;
    cin >> n >> a >> b >> c >> d >> e;
    long long m = min(a,min(b,min(c,min(d, e))));
    long long waiting = 0;
    if(n > m){
        if(n%m != 0) waiting = n/m;
        else waiting = n/m - 1;
    }
    cout << 5 + waiting << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

p1 = 0
for i in range(n):
    p1 += abs(x[i] - y[i])
print(p1)

p2 = 0
for i in range(n):
    p2 += abs(x[i] - y[i]) ** 2
print(p2 ** 0.5)

p3 = 0
for i in range(n):
    p3 += abs(x[i] - y[i]) ** 3
print(p3 ** (1 / 3))

p4 = []
for i in range(n):
    p4.append(abs(x[i] - y[i]))

print(max(p4))



Measured memory_bytes: 5648
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int n, cnt;
char s[100005];

int main() {
	scanf("%s", s);
	n = strlen(s);
	s[n] = 'a';
	cnt = 0;
	for (int i = 1; i <= n; i++)
		cnt += (s[i] != s[i - 1]);
	printf("%d\n", cnt - 1);
	return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] num = new int [3];
        for(int i = 0;i < 3;i++){
            num[i] = sc.nextInt();
        }
        int count5 = 0;
        int count7 = 0;
        for(int i = 0;i < 3;i++){
            if((num[i] != 5) && (num[i] != 7)){
                System.out.println("NO");
                return;
            }
            else if (num[i] == 5){
                count5++;
            }
            else if (num[i] == 7){
                count7++;
            }
        }
        if((count5 == 2) && (count7 ==1)){
            System.out.println("YES");
        }
        else{
            System.out.println("NO");
        }
        return;
    }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll, vl/*, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, n) for(ll i = 1; i <= ll(n); ++i)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); ++i)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); ++i)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  string S;
  cin >> S;
  rep(i, 8) {
    if(S.substr(0, i) + S.substr(S.size()-7+i)=="keyence") goto ABLE;
  }
  cout << "NO" << newl;
  return 0;
  
  ABLE:
  cout << "YES" << newl;
  return 0;
}


Measured memory_bytes: 256