akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env ruby

INF=1<<100

if $0 == __FILE__
  n, k = gets.split(' ').map &:to_i
  h = gets.split(' ').map &:to_i

  dp = Array.new(n, INF)
  dp[0] = 0

  (1..(n-1)).each do |i|
    dp[i] = INF
    (1..k).each do |kk|
      next if i-kk < 0
      value = dp[i-kk] + (h[i] - h[i-kk]).abs
      dp[i] = value if value < dp[i]
    end
  end

  puts dp[n-1]
end


Measured memory_bytes: 13348
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
const int MOD = 1e9+7;
template<typename T> 
struct BIT{
  int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(int n_,T d):n(n_),bit(n_+1,d){}
  
  T sum(int i){
    T s=bit[0];
    for(int x=i;x>0;x-=(x&-x))
      (s+=bit[x])%=MOD;
    return s;
  }
  void add(int i,T a){
    if(i==0) return;
    for(int x=i;x<=n;x+=(x&-x))
      (bit[x]+=a)%=MOD;
  }
  T sum0(int i){
    return sum(i+1);
  }
  void add0(int i,T a){
    add(i+1,a);
  }
};


template<typename T>
vector<T> compress(vector<T> v){
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  return v;
}

template<typename T>
map<T, int> dict(const vector<T> &v){
  map<T, int> res;
  for(int i=0;i<(int)v.size();i++)
    res[v[i]]=i;
  return res;
}

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  vector<Int> x(n),y(m);
  for(Int i=0;i<n;i++) cin>>x[i];
  for(Int i=0;i<m;i++) cin>>y[i];

  using P = pair<Int, Int>;
  vector<P> vp;
  for(Int i=0;i<n;i++){
    if(x[i]<y[0]||y[m-1]<x[i]) continue;
    Int k=lower_bound(y.begin(),y.end(),x[i])-y.begin();
    vp.emplace_back(x[i]-y[k-1],x[i]-y[k]);
  }
  vp=compress(vp);
  
  vector<Int> b;
  b.emplace_back(0);
  for(auto p:vp) b.emplace_back(-p.second);
  b=compress(b);
  auto mb=dict(b);
  
  m=b.size();
  BIT<int> bit(m+1,0);
  bit.add0(0,1);
  
  for(auto p:vp){
    Int y=mb[-p.second];
    bit.add0(y,bit.sum0(y-1));
  }
  
  cout<<bit.sum0(m)<<endl;
  return 0;
}


Measured memory_bytes: 9952
N = int(input())
s_list = []
s_set = []

for i in range(N):
	s_list.append(list(x for x in input()))

for i in s_list:
	s_set.append(set(i))

result_char = {x for x in 'qwertyuiopasdfghjklzxcvbnm'}

for i in range(N-1):
	result_char = (s_set[i] & s_set[i+1] & result_char)

result_char = list(result_char)
result_char.sort()

result = ''
for i in result_char:
	count = min(x.count(i) for x in s_list)
	result += i*count
print(result)

Measured memory_bytes: 3188
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, L):
    L.sort()
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if L[i] == L[j]: continue
            for k in range(j + 1, N):
                if L[i] == L[k] or L[j] == L[k]: continue
                if L[i] + L[j] > L[k]:
                    ans += 1
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *L, = map(int, input().split())
    main(N, L)


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

using ll = long long;
// #define int long long

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))

bool already_ac[100005] = {};
int penas[100005] = {};

/***** MAIN *****/
signed main() {
  int n, m;
  cin >> n >> m;
  
  int sub_target[m+1];
  bool sub_ac[m+1];
  REP(i,m) {
    string tmp;
    cin >> sub_target[i] >> tmp;
    if(tmp == "AC") sub_ac[i] = true;
    else sub_ac[i] = false;
  }
  int pena = 0;
  int point = 0;
  REP(i,m) {
    if(already_ac[sub_target[i]]) continue;

    if(sub_ac[i]) {
      ++point;
      already_ac[sub_target[i]] = true;
    }
    else ++penas[sub_target[i]];
  }
  REPS(i,1,n+1) {
    if(already_ac[i]) pena += penas[i];
  }

  cout << point << " " << pena;

  
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<ll, ll, ll> T;

char c;

int main(void){
    
    scanf("%c", &c);
    if(c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o') printf("vowel\n");
    else printf("consonant\n");
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(ll i=0;i<n;i++)
#define ll long long
using namespace std;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
signed main() {
	ll k, a, b;
	cin >> k >> a >> b;
	if (a > b || abs(a - b) <= 2)cout << k + 1 << endl;
	else if (k <= a)cout << k + 1 << endl;
	else cout << (k - (a - 1)) / 2 * (b - a) + a+(k - (a - 1))%2 << endl;
	getchar(); getchar(); return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int n,num,card[4][13];
    cin >> n;
    char A;
    for(int a = 0; a < 4; a ++){
        for(int b = 0;b < 13; b ++){
            card[a][b] = 0;
        }
    }
    for(int i = 0; i < n; i ++){
        cin >> A >> num;
        if(A == 'S') card[0][num - 1] = 1;
        if(A == 'H') card[1][num - 1] = 1;
        if(A == 'C') card[2][num - 1] = 1;
        if(A == 'D') card[3][num - 1] = 1;
    }
    for(int j = 0; j < 4; j++){
        for(num = 0; num < 13; num ++){
            if(card[j][num] == 0 & j == 0)cout << "S" << " " << num + 1 << endl;
            if(card[j][num] == 0 & j == 1)cout << "H" << " " << num + 1 << endl;
            if(card[j][num] == 0 & j == 2)cout << "C" << " " << num + 1 << endl;
            if(card[j][num] == 0 & j == 3)cout << "D" << " " << num + 1 << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3088
#include<iostream>
#include<cstdio>
using namespace std;
int a[1010],sum1[1010],sum2[1010],sum[1010];long long Sum1=0,Sum2=0,Sum;int cnt2=0,cnt1=0,cnt=0;
int ans[1010],Cnt=0;
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i+=2)if(a[i]>0)sum1[++cnt1]=i,Sum1+=a[i];
	for(int i=2;i<=n;i+=2)if(a[i]>0)sum2[++cnt2]=i,Sum2+=a[i];
	if(Sum1>Sum2){for(int i=1;i<=cnt1;i++)sum[i]=sum1[i];Sum=Sum1;cnt=cnt1;}
	else {for(int i=1;i<=cnt2;i++)sum[i]=sum2[i];Sum=Sum2;cnt=cnt2;}
	if(Sum==0)
	{
		int Max=-1e9-7,id;
		for(int i=1;i<=n;i++)if(a[i]>Max)Max=a[i],id=i;
		printf("%d\n",Max);
		for(int i=n;i>id;i--)ans[++Cnt]=i;
		for(int i=1;i<id;i++)ans[++Cnt]=1;
		printf("%d\n",Cnt);
		for(int i=1;i<=Cnt;i++)printf("%d\n",ans[i]);
		return 0; 
	}
	printf("%lld\n",Sum);
	int l=sum[1],r=sum[cnt],K=0;
	for(int i=n;i>r;i--)ans[++Cnt]=i;
	for(int i=1;i<l;i++)ans[++Cnt]=1;
	for(int i=2;i<=n;i++)
	{
		K++;
		int mid=(sum[i]-sum[i-1])>>1;
		for(int j=mid;j>=1;j--)ans[++Cnt]=1+j;
	}
	printf("%d\n",Cnt);
	for(int i=1;i<=Cnt;i++)printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;

struct Node {
  int key;
  Node *right, *left, *parent;
};

Node *root, *NIL;

void insert(int k) {
  Node *y = NIL;
  Node *x = root;
  Node *z;

  z = (Node *)malloc(sizeof(Node));
  z -> key = k;
  z -> left = NIL;
  z -> right = NIL;

  while ( x != NIL ) {
    y = x;
    if ( z->key < x->key ) {
      x = x->left;
    } else {
      x = x->right;
    }
  }

  z->parent = y;
  if ( y == NIL ) {
    root = z;
  } else {
    if ( z->key < y->key ) {
      y->left = z;
    } else {
      y->right = z;
    }
  }
}

void inorder(Node *u) {
  if ( u == NIL ) return;
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}
void preorder(Node *u) {
  if ( u == NIL ) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}

int main() {
  int n, i, x;
  string com;

  scanf("%d", &n);

  for ( i = 0; i < n; i++ ) {
    cin >> com;
    if ( com == "insert" ) {
      scanf("%d", &x);
      insert(x);
    } else if ( com == "print" ) {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}


Measured memory_bytes: 26736
#include<stdio.h>
int main(void)
{
	char s[3];
	int n,i,cnt;
	cnt=0;
	for(i=0;i<3;i++){
		scanf("%c",&s[i]);
		if(s[i]=='o'){
			cnt++;
		}
	}
	n=700+(cnt*100);
	printf("%d\n",n);
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int d[10][10];
int t[10][10];
int n;
int i,j;
int res;

int main(){
	while(1){
	scanf("%d",&n);
	if(n==0)return 0;
	for(i=0;i<n;i++)for(j=0;j<n;j++){
		scanf("%d",&d[i][j]);
		t[i][j]=0;
	}
	for(i=0;i<n;i++){
		res=0;
		for(j=0;j<n;j++){
			res+=d[i][j];
			printf("%5d",d[i][j]);
		}
		printf("%5d\n",res);
	}
	for(i=0;i<n;i++){
		res=0;
		for(j=0;j<n;j++){
			res+=d[j][i];
		}
		printf("%5d",res);
	}
	res=0;
	for(i=0;i<n;i++)for(j=0;j<n;j++){
		res+=d[i][j];
	}
	printf("%5d\n",res);
	}
}

		

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

int n, m;
pair<int,int> p[100005];

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0; i<m; i++) {
		scanf("%d%d", &p[i].second, &p[i].first);
	}
	sort(p, p+m);
	int ans=0;
	int last=-1;
	for(int i=0; i<m; i++) {
		int a=p[i].second, b=p[i].first;
		if(a>=last) {
			last=b;
			ans++;
		}
	}
	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 1024
import java.util.*;


public class Main {
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String line = sc.next();
		if (line.equals(line.toLowerCase())) {
		    System.out.println("a");
		} else {
		    System.out.println("A");
		}
		
    }
}

Measured memory_bytes: 35484
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        Reader r = new Reader();    
        int N, M;
        {int[] temp = r.ii(); N = temp[0]; M = temp[1];}
        int[] A = r.ii();
        int[][] BC = new int[M][2];
        long bSize = 0;
        for(int i = 0; i < M; i++){
            BC[i] = r.ii();
            bSize += BC[i][0];
        }
        Arrays.sort(A);
        Arrays.sort(BC, (x, y) -> -x[1]+y[1]);
        int[] D = new int[(int)Math.min(N, bSize)];
        for(int i = 0, j = 0; i < D.length; i++){
            if(BC[j][0] < 1)
                j++;
            D[i] = BC[j][1];
            BC[j][0]--;
        }
        for(int i = 0; i < D.length && A[i] < D[i]; i++)
            A[i] = D[i];
        long ans = 0;
        for(long a : A)
            ans += a;
        println(ans);
    }

    static void print(Object o){
        System.out.print(o.toString());
    }

    static void println(Object o){
        System.out.println(o.toString());
    }

    static int Int(String s){
        return Integer.parseInt(s);
    }

    static long Long(String s){
        return Long.parseLong(s);
    }
    static class Reader extends BufferedReader{
        Reader(){
            super(new InputStreamReader(System.in));
        }

        String s() throws IOException{
            return readLine();
        }

        String[] ss() throws IOException{
            return s().split(" ");
        }

        int i() throws IOException{
            return Int(s());
        }

        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Int(ss[j]);
            return ii;
        }

        long l() throws IOException{
            return Long(s());
        }

        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long(ss[j]);            
            return ll;
        }
    }
}


Measured memory_bytes: 53180
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
//typedef vector<unsigned int>vec;
typedef vector<ll>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int W, H;
    cin >> W >> H;
    vector<pair<ll,int>> pq;
    REP(i,W){
        ll p;
        cin >> p;
        pq.push_back({p, 0});
    }
    REP(i,H){
        ll p;
        cin >> p;
        pq.push_back({p, 1});
    }
    sort(pq.begin(),pq.end());
    ll ans = 0;
    W++, H++;
    for(auto x : pq){
        if(x.second == 1){
            ans += W * x.first;
            H--;
        }
        else{
            ans += H * x.first;
            W--;
        }
    }
    cout << ans << endl;
}

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

ll n, ans=0;

void dfs(ll val, ll a, ll b, ll c){
  if(val > n) return;
  if(a && b && c) ans++;
  dfs(val*10+7, 1, b, c);
  dfs(val*10+5, a, 1, c);
  dfs(val*10+3, a, b, 1);
}

int main() {
  cin >> n;
  dfs(0,0,0,0);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include<stack>
#include<queue>

#define ll long long int
#define all(x) x.begin(), x.end()
#define MOD 1000000007


using namespace std;



void solve()
{
    ll N, K;
    cin >> N >> K;
    ll max = N * (N + 1) / 2;
    ll min = N * (N + 1) / 2;

    max %= MOD;
    min %= MOD;

    ll x = N;
    ll y = 0;
    ll count = 0;
    for (int i = K; i <= N + 1; i++)
    {
        count += max - min + 1;
        count %= MOD;
        min -= x;
        max -= y;
        x--;
        y++;
    }

    cout << count << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}



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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x;
    cin >> x;
    if (x == 5 || x == 7 || x == 3)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
     


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,e) for(int i=0;i<(e);i++)

int main(void) {
  int H,W,N;
  int Sr,Sc;
  string S,T;
  cin >> H >> W >> N >> Sr >> Sc >> S >> T;
  Sr--; Sc--;
  int mem[2][2]={{-1,H},{-1,W}};
  rep(i,N){
    if(T[N-1-i]=='U'&&mem[0][1]<H) mem[0][1]++;
    if(S[N-1-i]=='D'&&mem[0][1]>-1) mem[0][1]--;
    if(mem[0][1]==0) break;
    if(T[N-1-i]=='D'&&mem[0][0]>-1) mem[0][0]--;
    if(S[N-1-i]=='U'&&mem[0][0]<H) mem[0][0]++;
    if(mem[0][0]==H-1) break;
    if(mem[0][1]-mem[0][0]==1) break;
  }
  rep(i,N){
    if(T[N-1-i]=='L'&&mem[1][1]<W) mem[1][1]++;
    if(S[N-1-i]=='R'&&mem[1][1]>-1) mem[1][1]--;
    if(mem[1][1]==0) break;
    if(T[N-1-i]=='R'&&mem[1][0]>-1) mem[1][0]--;
    if(S[N-1-i]=='L'&&mem[1][0]<W) mem[1][0]++;
    if(mem[1][0]==W-1) break;
    if(mem[1][1]-mem[1][0]==1) break;
  }
  if(mem[0][0]<Sr&&mem[0][1]>Sr&&mem[1][0]<Sc&&mem[1][1]>Sc)
    cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 776
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

n, d = map(int, input().split())
x = []
for _ in range(n):
    x.append(list(map(int, input().split())))
cnt = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans = 0.0
        for k in range(d):
            ans += (x[i][k] - x[j][k])**2
        if sqrt(ans).is_integer():
            cnt += 1
        #print(i, j, sqrt(ans), sqrt(ans).is_integer())
print(cnt)

Measured memory_bytes: 5044
# coding:utf-8

import sys
from collections import Counter

input = sys.stdin.readline
INF = float('inf')


def inpl(): return list(map(int, input().split()))


N = int(input())
S = input().strip()

num_E = Counter(S)['E']  # リーダより右側にいるEの数
num_W = 0  # リーダより左側にいるWの数

ans = N - 1
for i in range(N):
    if S[i] == 'E':
        num_E -= 1
        ans = min(ans, num_W + num_E)
    else:
        ans = min(ans, num_W + num_E)
        num_W += 1

print(ans)


Measured memory_bytes: 4084
#include <iostream>
#include <string>

int main()
{
    std::string S;
    int N;
    std::cin >> N >> S;

    auto s = S.c_str();

    for(int i=0;i<S.size(); i++)
    {
        S[i] = (S[i]+N);
        if(S[i]>90) S[i] = (S[i]%90)+64;
    }
    std::cout << s <<'\n';
}


Measured memory_bytes: 256
import java.util.Scanner

fun main(args: Array<String>) {
	val scn = Scanner(System.`in`)
	val n = scn.nextInt()
	val s = scn.next()
	var bef = s[0]
	var ans = 1
	for (i in 1 until s.length){
		if (s[i]!=bef) {
			ans++
			bef = s[i]
		}
	}
	println(ans)
}

Measured memory_bytes: 32620
#include<iostream>
using namespace std;
 
int main(){
 	 
  string s;
  int a;
  cin >> s >> a;
  for(int i=0;i<4;++i){
  	if(s[i] == '+'){
    	a++; 
    }else{
     	a--; 
    }
  }
  cout << a << endl;
  
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=200010;
int a[maxn],b[maxn];
int n,m;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	sort(a+1,a+1+n);
	sort(b+1,b+1+m);
	int j=1;
	for(int i=1;i<=n;i++){
		if(a[i]==b[j]) j++;
	}
	if(j==m+1) puts("YES");
	else puts("NO");
	return 0;
}

Measured memory_bytes: 1664
#include<stdio.h>
#include<math.h>
#define PI 3.14159265
int main(void)
{
	double a,b,c,x;
	double s,l,h;
	
	scanf("%lf%lf%lf",&a,&b,&c);
	c=c/360*2*PI;
	s=a*b*sin(c)/2;
	printf("%f\n",s);
	x=sqrt(a*a+b*b-2*a*b*cos(c));
	l=a+b+x;
	printf("%f\n",l);
	h=b*sin(c);
	printf("%f\n",h);

	return 0;
}


Measured memory_bytes: 676
n=int(input())
blue=[]
for i in range(n):
    blue.append(input())
m=int(input())
red=[]
for i in range(m):
    red.append(input())
max=0
for i in blue:
    b=blue.count(i)
    r=red.count(i)
    if b-r>max:max=b-r
print(max)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define PI 3.14159265358979
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repp(i, s, e) for(int i = (s); i <= (e); ++i)
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define FAST_IO() ios::sync_with_stdio(0); cin.tie(0)
template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) { for (auto x : v) os << x << " "; return os << "\n"; }
template<class U, class V>
ostream& operator<<(ostream &os, const pair<U, V> &p) { return os << "(" << p.first << "," << p.second << ")";}

const int MAXN = 1e5;
const int MOD = 1e9 + 7;
int N, K;
vector<int> adj[MAXN];
int parent[MAXN];
vector<int> childs[MAXN];
ll cnt[MAXN];

void dfs(int curr, int prev) {
    parent[curr] = prev;
    for(auto &next : adj[curr]) {
        if(parent[next] == -1 && next != prev) {
            dfs(next, curr);
            childs[curr].push_back(next);
        }
    }
}

ll count(int root) {
    ll &ret = cnt[root];
    if(ret != -1) return ret;
    if(sz(childs[root]) + 2 > K) return 0;
    ret = 1;
    rep(i, sz(childs[root])) {
        ret = (ret * (K - 2 - i) % MOD * count(childs[root][i])) % MOD;
    }
    return ret;
}

int main() {
    FAST_IO();
    cin >> N >> K;
    rep(i, N - 1) {
        int u, v; cin >> u >> v;
        adj[u - 1].push_back(v - 1);
        adj[v - 1].push_back(u - 1);
    }
    // Make Tree
    memset(parent, -1, sizeof(parent));
    dfs(0, -1);
    // count coloring
    memset(cnt, -1, sizeof(cnt));
    if(sz(childs[0]) + 1 > K) {
        cout << "0\n";
    } else {
        ll ans = K;
        rep(i, sz(childs[0])) {
            ans = (ans * (K - 1 - i) % MOD * count(childs[0][i])) % MOD;
        }
        cout << ans << "\n";
    }
}

Measured memory_bytes: 17024
#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
#include<fstream>
#include <set>
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
const int  MAXN =1e5+10;
const long long  mod = 1e14 ;
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf= 0x3f3f3f3f;
#define eps 1e-8
#define PI 3.1415926535898
#define lowbit(x) (x&(-x))
using namespace std ;
//getline(cin,s);
//set<ll>::iterator it;
//map<int,int>::iterator it;
typedef long long ll;
typedef unsigned long long ull;
//unordered_map<int,int>mp;
//int need[MAXN];
//map<int,int>mp;
//TLE了 可能思路：每个数*一个数的形式 判断所得的num 然后与n比较 
//这道题注意点：O() 在数据范围小的情况下 尽量开普通数组 然后 是unordered_map（查找快，无序） 最后是map
//自己老是习惯开map 然后tle 不知所措 
int dist[MAXN];
vector<int>ve[MAXN];
int vis[MAXN];
int sign[MAXN];
int main()
{
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++) dist[i]=inf;
	while(k--)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		ve[x].push_back(y);
		ve[y].push_back(x);
	}
	queue<int> q;
	dist[1]=0;
	q.push(1);vis[1]=1;
	while(q.size())
	{
		int now=q.front();
		q.pop();vis[now]=0;
		for(int i=0;i<ve[now].size();i++)
		{
			int ne=ve[now][i];
			if(dist[ne]>dist[now]+1)
			{
				dist[ne]=dist[now]+1;
				sign[ne]=now;
				if(!vis[ne])
				{
					vis[ne]=1;
					q.push(ne);
				}
			}
		} 
	}
	for(int i=2;i<=n;i++) 
	{
	    if(dist[i]==inf)
	    {
	    	printf("No\n");
	    	return 0;
		} 
	} 
	printf("Yes\n");
	for(int i=2;i<=n;i++) printf("%d\n",sign[i]);
	return 0;	
} 

Measured memory_bytes: 11472
def solve(s):
    acgt = ['A','C','G','T']
    ans = 0
    c = 0

    for si in s:
        if si in acgt:
            c += 1
        else:
            ans = c if c>ans else ans
            c = 0
    ans = c if c>ans else ans
    return ans


if __name__ == '__main__':
    s = input()
    print(solve(s))


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] ary = new int[n];
		for(int i = 0; i < n; i++){
			ary[i] = sc.nextInt();
		}
		String s = "" + ary[n - 1];
		for(int i = n - 2; i >= 0; i--){
			s += " " + ary[i];
		}
		System.out.println(s);
	}
}



Measured memory_bytes: 26384
#include "bits/stdc++.h"
using namespace std;
 
////////////// Prewritten code follows. Look down for solution. ////////////////

#define fs first
#define sc second
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;

template<typename T>
const T INF = (is_same<T, int>::value ? 1e9 : 1e18);
template<typename T>
inline T mod(T n, T mod){ T res = n%mod; if(res < 0) res += mod; return res; }

/// command for char arrays with spaces -> scanf(" %[^\n]", text);
 
////////////////////////// Solution starts below. //////////////////////////////

int main(){
	fastio;
	int n, k;
	cin >> n >> k;
	vector<double> v(n+1), value(n+1);
	for(int i = 1; i <= n; i++){
		cin >> v[i];
		value[i] = (v[i]*(v[i]+1)/2)/v[i];
		value[i] += value[i-1];
	}
	double ans = 0;
	for(int i = k; i <= n; i++){
		ans = max(value[i] - value[i-k], ans);
	}
	cout << setprecision(10) << fixed << ans << endl;
	return 0;
}

Measured memory_bytes: 3456
#include <stdio.h>

int main(){
	int n,i;
	long long int money;

	scanf("%d",&n);

	money = 100000;

	for(i = 0;i < n;i++){
		money *= 105;
		money /= 100;
		money += 999;
		money /= 1000;
		money *= 1000;
	}

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

	return 0;
}

Measured memory_bytes: 592
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
  static InputReader in;
  static PrintWriter out;

  static class Solution {
    void solve() throws IOException {
      BufferedReader br2 = new BufferedReader(new InputStreamReader(System.in));
      String words = br2.readLine();
      int length = words.length();
      char[] converted = new char[length];
      
      for (int i = 0; i < length; i++) {
        if (Character.isUpperCase(words.charAt(i))) {
          converted[i] = Character.toLowerCase(words.charAt(i));
        } else if (Character.isLowerCase(words.charAt(i))){
          converted[i] = Character.toUpperCase(words.charAt(i));
        } else {
          converted[i] = words.charAt(i);
        }
      }
        
      for (int i = 0; i < length; i++) {
        out.print(converted[i]);
      }
      
      out.print("\n");
//      End solve()
    }
//    End Solution
}

  public static void main(String[] args) throws IOException {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out);
    Solution solver = new Solution();
    solver.solve();
    out.close();
}

  static class InputReader {
    public BufferedReader br;
    public StringTokenizer st;

    public InputReader(InputStream stream) {
      br = new BufferedReader(new InputStreamReader(stream));
    }

    public int nextInt() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return Integer.parseInt(st.nextToken());
    }

    public long nextLong() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return Long.parseLong(st.nextToken());
    }

    public String next() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return st.nextToken();
    }

    public double nextDouble() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return Double.parseDouble(st.nextToken());
    }


  }

}

Measured memory_bytes: 24368
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
 
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import queue
 
NINF = -1000000000
 
def reachable(n, vtxs):
    visited = [0 for i in range(n)]
    visited[0] = 1
 
    qu = queue.Queue()
    qu.put(0)
    while(not qu.empty()):
        curr = qu.get()
        for next in vtxs[curr]:
            if visited[next] == 0:
                visited[next] = 1
                qu.put(next)
 
    return visited
 
def reachable_rev(n, revs):
    visited = [0 for i in range(n)]
    visited[n-1] = 1
    qu = queue.Queue()
    qu.put(n - 1)
    while(not qu.empty()):
        curr = qu.get()
        for next in revs[curr]:
            if visited[next] == 0:
                visited[next] = 1
                qu.put(next)
 
    return visited
 
 
 
def bellman(n, m, edges, vtxs, revs):
    cost = [NINF for i in range(n)]
    cost[0] = 0
    tgts = [0]
    loop = 0
    final = False
    reach = reachable(n, vtxs)
    revreach = reachable_rev(n, revs)
    while(True):
        flag = False
        if loop > n:
            final = True
            break
        for e in edges:
            # print(e, cost)
            if cost[e[1]] < cost[e[0]] + e[2]:
                point = e[1]
                ppoint = e[0]
                # print("point", point)
                if reach[point] and revreach[point]:
                    if reach[ppoint] and revreach[ppoint]:
                        cost[e[1]] = cost[e[0]] + e[2]
                        flag = True
                        # print("update")
        if not flag:
            break
        loop += 1
        # print("loop", loop, cost)
 
 
    # print("judge", reach, revreach)
    if final:
        for e in edges:
            # print(e, cost)
            if cost[e[1]] < cost[e[0]] + e[2]:
                point = e[1]
                ppoint = e[0]
                # print("point", point)
                if reach[point] and revreach[point]:
                    if reach[ppoint] and revreach[ppoint]:
                        return -1
 
    if reach[-1] == 0:
        return -1
 
    return max(0, cost[-1])
 
n, m , p= getList()
vtxs = [[] for i in range(n)]
revs = [[] for i in range(n)]
edges = []
 
for i in range(m):
    a, b, c = getList()
    vtxs[a-1].append(b-1)
    revs[b-1].append(a-1)
    edges.append((a-1, b-1, c - p))
 
# print(edges)
print(bellman(n, m, edges, vtxs, revs))

Measured memory_bytes: 56552
package main
 
import (
	"fmt"
	"strings"
)
 
func main() {
	var s string
	fmt.Scan(&s)
  	
  	head := strings.Index(s, "A")
  	end  := strings.LastIndex(s, "Z")
  
  	ans := end - head + 1
	fmt.Printf("%d\n", ans)
}

Measured memory_bytes: 3292
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s1 = sc.next();
		String s2 = sc.next();
		char[] chars1 = s1.toCharArray();
		Arrays.sort(chars1);
		char[] chars2 = s2.toCharArray();
		Arrays.sort(chars2);
		String ns1 = new String(chars1);
		String ns2 = new String(chars2);
		StringBuilder sb = new StringBuilder(ns2);
		ns2 = sb.reverse().toString();
		if(ns1.compareTo(ns2) < 0) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 21844
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
const double EPS = 1e-10;

signed main() {
	string s; cin >> s;
	string ans;
	bool f(false);
	rep(i, 0, s.size()) {
		if (f == false) {
			if (s[i] == 'A') {
				ans.push_back(s[i]);
				f = true;
			}
		}
		else {
			if (s[i] == 'Z') {
				ans.push_back(s[i]);
				f = false;
			}
		}
	}
	f = false;
	for (int i = 0; i + 1 < ans.size(); i++) {
		if (ans[i] == 'A'&&ans[i + 1] == 'Z') {
			cout << "AZ";
			f = true;
			i++;
		}
	}
	if (f == false)cout << -1;
	cout << endl;
	return 0;
}

Measured memory_bytes: 3208
<?php
error_reporting(0);
$stdin = file_get_contents('php://stdin');
$line = explode("\n",$stdin);
$fi = 0;
$cnt = 0;
$list = array();
$key = new stdclass();
foreach($line as $l) {
  if (strlen($l)==0) continue;
  if ($fi == 0) {
    $a = explode(" ",$l);
    $key->A = $a;
    $fi++;
    continue;
  }
  if ($fi > 0) {
    $a = explode(" ",$l);
    $key->X[] = $a;
  }
}
$N = $key->A[0];
$A = $key->A[1];
$B = $key->A[2];

if ($A > $B) {
  printf("0\n");
  exit;
}
if ($N==1) {
  if ($A != $B) {
    printf("0\n");
    exit;
  }
  else {
    printf("1\n");
    exit;
  }
}
printf("%d\n",($B-$A)*($N-2)+1);


Measured memory_bytes: 3828
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
	int n, ans = 0, cur = 0;
  	string s;
  	cin >> n >> s;
  	for(char c: s) {
      if (c == 'I')
        cur += 1;
      else
        cur -= 1;
      ans = max(ans, cur);
    }
  	cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) (a).begin(),(a).end()
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;

	vector<vector<long long>>dp(n,vector<long long>(n,0));

	vector<int>arr(n);
	for(int& i:arr) cin >> i;

	for(int l=n-1;l>=0;l--){
		for(int r=l;r<n;r++){
			if(l == r){
				dp[l][r] = arr[l];
			}else{
				dp[l][r] = max(arr[l]-dp[l+1][r],arr[r]-dp[l][r-1]);
			}
		}
	}

	cout << dp[0][n-1] << endl;

	return 0;
}


Measured memory_bytes: 73712
#include <bits/stdc++.h>
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a)%MOD)+((b)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define EPS (1e-20)
#define INF 2147483647
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using VLL = std::vector<llint>;
using MCI = std::map<char, int>;
using VPII = std::vector<PII>;
using namespace std;


int N;
int p[100010];


int solve(){
	int ans = 0;
	rep(i, 0, N-1)
		if(p[i] == i) swap(p[i], p[i+1]), ans++;
	if(p[N-1] == N-1) ans++;
	return ans;
}


signed main(){
	cin >> N;
	rep(i, 0, N) cin >> p[i], p[i]--;

	cout << solve() << endl;

	return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1189&lang=jp
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define INF 1<<30
#define MAX_M 1000010
bool Prime[MAX_M];
int Caves[1002][1002];
pii dp[1002][1002];

void init_prime() {
	Prime[2] = true;
	for (int i = 3; i < MAX_M; i += 2) {
		bool f = false;
		for (int j = 2; j*j <= i;j++) {
			if (i%j == 0) { f = true; break; }
		}
		if (!f) Prime[i] = true;
	}
}

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

pair<int,int> init_Caves(int m,int n) {
	/* Caves initialize */
	memset(Caves, 0, sizeof(Caves));
	/* initial state */
	int x, y; x = y = 500;
	/* next direction */
	int k = 0;
	/* step valiables */
	int steps = 1;
	int now_steps = 0;
	int count = 0;
	/* return valiables */
	pii ret;
	for (int i = 1; i <= m;i++) {
		/* n locate & Caves */
		if (i == n) ret = { y,x };
		Caves[y][x] = i;

		/* next locate */
		x += dx[k]; y += dy[k];

		/* step */
		now_steps++;
		if (steps == now_steps) {
			now_steps = 0;
			k = (k + 1) % 4;
			count = (count + 1) % 2;
			if (count == 0) {
				steps++;
			}
		}
	}
	return ret;
}

int dcx[3] = { -1,0,1 };
int dcy[3] = { -1,-1,-1 };

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

	int m, n;
	while (cin >> m >> n, m | n) {
		memset(dp, -1, sizeof(dp));
		auto s = init_Caves(m, n);
		if (Prime[n]) {
			dp[s.first][s.second] = { 1,n };
		}
		else {
			dp[s.first][s.second] = { 0,0 };
		}
		pii ans = { 0,0 };

		for (int y = 1000; y >= 1; y--) {
			for (int x = 1; x <= 1000; x++) {
				if (Caves[y][x] == 0) continue;
				if (dp[y][x].first == -1 && dp[y][x].second == -1) continue;

				if (dp[y][x].first > ans.first) {
					ans.first = dp[y][x].first;
					ans.second = dp[y][x].second;
				}
				else if (dp[y][x].first == ans.first && dp[y][x].second > ans.second) {
					ans.second = dp[y][x].second;
				}

				int cave_count = dp[y][x].first;
				int last_prime = dp[y][x].second;
				for (int k = 0; k < 3;k++) {
					int ny = y + dcy[k], nx = x + dcx[k];
					int next_cave_count = cave_count + (Prime[Caves[ny][nx]] == true);
					int next_last_prime = Prime[Caves[ny][nx]] ? Caves[ny][nx] : last_prime;
					if (next_cave_count > dp[ny][nx].first) {
						dp[ny][nx].first = next_cave_count;
						dp[ny][nx].second = next_last_prime;
						continue;
					}
					if (next_cave_count == dp[ny][nx].first && next_last_prime > dp[ny][nx].second) {
						dp[ny][nx].second = next_last_prime;
						continue;
					}
				}
			}
		}


		cout << ans.first << " " << ans.second << endl;
	}
}

Measured memory_bytes: 15892
#include <cstdio>

int main()
{
    int n, m;
    int A[100][100], b[100];
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i++) //行列Aへの入力
    {
        for (int j = 0; j < m; j++)
            scanf("%d", &A[i][j]);
    }

    for (int j = 0; j < m; j++) //行列bへの入力
        scanf("%d", &b[j]);

    int sum[100]; //行列の計算、出力
    for (int i = 0; i < n; i++)
    {
        sum[i] = 0;
        for (int j = 0; j < m; j++)
        {
            sum[i] += A[i][j] * b[j];
        }
        printf("%d\n", sum[i]);
    }

    return 0;
}


Measured memory_bytes: 2756
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			while(sc.hasNext()) {
				int N=sc.nextInt();//構成員の数
				if(N==0) break;
				boolean[][] p=new boolean[110][110];//構成員が知っている個人情報
				for(int i=1; i<=N; i++) {
					int M=sc.nextInt();
					for(int j=0; j<M; j++) {
						int num=sc.nextInt();
						p[i][num]=true;
					}
				}
				
				int K=sc.nextInt();//漏洩した構成員の人数
				int[] k=new int[110];
				for(int i=1; i<=K; i++) {
					int l=sc.nextInt();
					for(int j=1; j<=N; j++) {
						if(p[j][l]) {
							k[j]++;
						}
					}
				}
				int end=0;
				int person=0;
				for(int i=1; i<=N; i++) {
					if(k[i]==K) {
						end++;
						person=i;
					}
				}
				if(end==1) {
					System.out.println(person);
				}
				else {
					System.out.println(-1);
				}
			}


		}
	}
}


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

struct UnionFind{
  Int n;
  vector<Int> r,p,b;
  UnionFind(){}
  UnionFind(Int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  UnionFind(Int sz,vector<Int> b):n(sz),r(sz,1),p(sz,0),b(b){
    iota(p.begin(),p.end(),0);
  }
  Int find(Int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(Int x,Int y){
    return find(x)==find(y);
  }
  void unite(Int x,Int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    b[x]+=b[y];   
    p[y]=x;
  }
};


template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  vector<Int> a(n),b(n);
  for(Int i=0;i<n;i++) cin>>a[i]>>b[i];
  vector<vector<Int> > G(n);
  for(Int i=0;i<m;i++){
    Int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }
  vector<Int> ord(n);
  iota(ord.begin(),ord.end(),0);
  sort(ord.begin(),ord.end(),
       [&](Int x,Int y){
	 return a[x]-b[x]<a[y]-b[y];
       });

  vector<Int> rev(n);
  for(Int i=0;i<n;i++) rev[ord[i]]=i;

  Int s=accumulate(b.begin(),b.end(),(Int)0);
  UnionFind uf(n,b);
  vector<Int> dp(n,0);
  for(Int v:ord){
    Int res=a[v]-b[v];
    for(Int t:G[v]){
      Int u=uf.find(t);
      if(rev[u]>rev[v]) continue;
      chmin(res,max(dp[u],a[v]-(uf.b[u]+b[v])));
    }
    //cout<<v<<":"<<a[v]-b[v]<<":"<<dp[v]<<endl;
    chmax(res,0);
    for(Int u:G[v])
      if(rev[u]<rev[v]) uf.unite(v,u);
    v=uf.find(v);
    dp[v]=res;
  }
  //cout<<dp[ord[n-1]]<<endl;
  cout<<s+dp[uf.find(ord[n-1])]<<endl;
  return 0;
}


Measured memory_bytes: 12544
// AOJ1055 Huge Family

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(){
	int n;
	while(cin >> n, n){
		vector< vector< pair<int, int> > > vp(n, vector< pair<int, int> >(2));
		for(int i=0;i<n;i++){
			for(int j=0;j<2;j++){
				int a, b; cin >> a >> b;
				vp[i][j] = make_pair(a,b);
			}
		}
		int ans = 1;
		vector<bool> vb(n, false);
		for(int i=0;i<n;i++){
			if(vb[i]) continue;
			vector<int> vi;
			queue<int> qu; qu.push(i);
			vb[i] = true;
			while(!qu.empty()){
				int t = qu.front(); qu.pop();
				for(int j=0;j<2;j++){
					vi.push_back(vp[t][j].second);
					int nxt = vp[t][j].first;
					if(!vb[nxt]){
						qu.push(nxt);
						vb[nxt] = true;
					}
				}
			}
			int cnt = 0;
			int m = vi[0];
			for(int j=0;j<vi.size();j++) m = max(m, vi[j]);
			for(int j=0;j<vi.size();j++)
				if(vi[j]==m) cnt++;
			ans = (ans*(cnt/2))%10007;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 0
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define PI 3.14159265359
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

int main() {
  int N;
  cin >> N;

  if (N == 2) {
    int A, B;
    cin >> A >> B;
    cout << A + B << endl;
  } else
    cout << "Hello World" << endl;

  return 0;
}


Measured memory_bytes: 256
N=int(input())
a=list(map(int,input().split()))
sum=0
for i in range(N):
    sum+=a[i]
ave=sum/N
ans=-1
min=100
for i in range(N):
    if min > abs(a[i]-ave):
        ans=i
        min=abs(a[i]-ave)
print(str(ans))

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

long long int x[200000], v[200000], path[200000], pathD[200000];

int main() {
	
	long long int N, C;
	long long int ans = 0;
	
	cin >> N >> C;
	
	for(int i = 0; i < N; i++){
		cin >> x[i] >> v[i];
	}
	
	path[0] = 0;
	path[1] = v[0] - x[0];
	for(int i = 1; i < N; i++){
		path[i + 1] = path[i] + v[i] - x[i] + x[i - 1];
	}
	
	for(int i = 1; i <= N; i++){
		path[i] = max(path[i], path[i - 1]);
	}
	
	reverse(x, x + N);
	for(int i = 0; i < N; i++){
		x[i] = C - x[i];
	}
	reverse(v, v + N);
	
	pathD[0] = 0;
	ans = max(ans, path[N]);
	pathD[1] = v[0] - 2 * x[0];
	ans = max(ans, pathD[1] + path[N - 1]);
	for(int i = 1; i < N; i++){
		pathD[i + 1] = pathD[i] + v[i] - 2 * (x[i] - x[i - 1]);
		ans = max(ans, pathD[i + 1] + path[N - i - 1]);
		//cout << pathD[i + 1] << " " << path[N - i - 1] << endl;
	}
	
	// check reverse direction
	
	path[0] = 0;
	path[1] = v[0] - x[0];
	for(int i = 1; i < N; i++){
		path[i + 1] = path[i] + v[i] - x[i] + x[i - 1];
	}
	
	for(int i = 1; i <= N; i++){
		path[i] = max(path[i], path[i - 1]);
	}
	
	reverse(x, x + N);
	for(int i = 0; i < N; i++){
		x[i] = C - x[i];
	}
	reverse(v, v + N);
	
	pathD[0] = 0;
	ans = max(ans, path[N]);
	pathD[1] = v[0] - 2 * x[0];
	ans = max(ans, pathD[1] + path[N - 1]);
	for(int i = 1; i < N; i++){
		pathD[i + 1] = pathD[i] + v[i] - 2 * (x[i] - x[i - 1]);
		ans = max(ans, pathD[i + 1] + path[N - i - 1]);
		//cout << pathD[i + 1] << " " << path[N - i - 1] << endl;
	}
	
	cout << ans << endl;
	
	return 0;
}



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

typedef long long ll;

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    rep(i, H) cin >> a[i];
    vector<bool> R(H, false), C(W, false);
    rep(i, H) {
        rep(j, W) {
            if (a[i][j] == '#') {
                R[i] = true;
                C[j] = true;
            }
        }
    }
    rep(i, H) {
        if (R[i]) {
            rep(j, W) {
                if (C[j]) cout << a[i][j];
            }
            cout << "\n";
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll a,b,c;
	scanf("%lld%lld%lld",&a,&b,&c);
	ll d=a*a+b*b+c*c-((a*b+b*c+c*a)*2);
	if(d>0&&c>a+b) printf("Yes");
	else printf("No");
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main () {

    string W;

    cin >> W;

    int cnt = 0;
    while (1) {
        string T; 
        cin >> T;

        if (T == "END_OF_TEXT") {
            break;
        }

        for (int i = 0; ; i++) {

            if (T[i] == 0) {
                break;
            }

            if ('A' <= T[i] && T[i] <= 'Z') {
                T[i] += 32;
            }
        }

        if (T == W) {
            cnt++;
            // cout << "count++" << endl;
        }
    }

    cout << cnt << endl;

    return 0;

}


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

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

    int N;
    cin >> N;
    if (N % 1000 == 0) {cout << 0 << "\n";}
    else {int inter = N / 1000;
    cout << (inter+1) * 1000 - N << '\n';
    }
    return 0;
}

Measured memory_bytes: 3652
import sys
import queue


class Dijkstra:
    class Edge:
        def __init__(self, end, cost):
            self.to = end
            self.cost = cost

    def __init__(self, node_size, inf):
        self._node = node_size
        self._graph = [[] for _ in range(self._node)]
        self.inf = inf
        self.dist = [self.inf for _ in range(self._node)]

    def add_edge(self, st, ed, cs):
        self._graph[st].append(self.Edge(ed, cs))

    def solve(self, start):
        que = queue.PriorityQueue()
        self.dist[start] = 0
        que.put((0, start))
        while not que.empty():
            cur_cost, cur_vertex = que.get()
            if self.dist[cur_vertex] < cur_cost:
                continue
            for e in self._graph[cur_vertex]:
                if self.dist[e.to] > cur_cost + e.cost:
                    self.dist[e.to] = cur_cost + e.cost
                    que.put((self.dist[e.to], e.to))


if __name__ == '__main__':
    V, E, r = map(int, sys.stdin.readline().split())
    dk = Dijkstra(V, 10 ** 10)
    for i in range(E):
        s, t, d = map(int, sys.stdin.readline().split())
        dk.add_edge(s, t, d)
    dk.solve(r)
    for value in dk.dist:
        if value == dk.inf:
            print("INF")
        else:
            print(value)


Measured memory_bytes: 141016
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
 string s;
  cin>>s;
  int a=s.size(),ans1=0,ans2=0,ans3=0,count=0;
  for(int i=2;i<a-1;i++){
if(s[i]=='C'){
  ans1=1;
  count+=1;
}
  }
  if(count!=1) ans1=0;
  
  if(s[0]=='A') ans2=1;
  for(int i=0;i<a;i++){
    if(s[i]!='A'&&s[i]!='C'&&s[i]>='B'&&s[i]<='Z') ans3=1;
  }
  if(ans1==1&&ans2==1&&ans3==0) cout<<"AC"<<endl;
  else cout<<"WA"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
using namespace std;
template<typename T>inline void read(T &x)
{
	T s=0,f=1;static char c;
	for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())s=s*10+(c^48);
	x=s*f;
}
const int MAXN=110;
static int n;
static int a[3][MAXN],dp[3][MAXN];
int main()
{
	read(n);
	Rep(i,1,2)Rep(j,1,n)read(a[i][j]);
	Rep(i,1,2)Rep(j,1,n)dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
	printf("%d\n",dp[2][n]);
	return 0;
}


Measured memory_bytes: 256