akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_in(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef int64_t ll;

int main() {
  int n,k,q;
  cin>>n>>k>>q;

  vector<int> correct(n,0);
  rep(i, q) {
    int ai;
    cin >> ai;
    correct[ai-1]++;
  }

  rep(i, n) {
    cout << (k-q+correct[i]>0?"Yes":"No") << endl;
  }
}


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

typedef long long ll;

ll inf = 1e9+7;
ll fact[200010] = {0};
ll inv[200010] = {0};

ll mult(ll n, ll m){
	if(m==1) return n%inf;
	else if(m%2==0){
		ll t = mult(n,m/2);
		return (t*t)%inf;
	}else{
		ll t = mult(n,m-1);
		return (t*n)%inf;
	}
}

ll N,M,K;
ll X[200010],Y[200010];

int main(){
    cin >> N >> M >> K;
    ll ans = 0;
    for(ll i=1;i<=N-1;i++){
        ll num = N-i;
        (ans += num*i%inf*M%inf*M%inf)%=inf;
    }
    for(ll i=1;i<=M-1;i++){
        ll num = M-i;
        (ans += num*i%inf*N%inf*N%inf)%=inf;
    }
    for(ll i=1;i<=K-2;i++){
        (ans *= (M*N-2)-(i-1))%=inf;
        (ans *= mult(i,inf-2))%=inf;
    }
    cout << ans << endl;
}

Measured memory_bytes: 2432
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] as = new int[n];
		for(int i=0; i<n; i++){
			as[i] = sc.nextInt();
		}
		boolean[] hantei = new boolean[1000001];
		Map<Integer, Integer> map = new HashMap<>();
		for (Integer key : as) {
    		Integer i = map.get(key);
    		map.put(key, i == null ? 1 : i + 1);
		}

		for (Map.Entry<Integer, Integer> i : map.entrySet()) {
			int ik = i.getKey();
			int iv = i.getValue();
			if(iv >= 2){
				int j = 2;
				int tmp = ik;
				while(tmp <= 1000000){
					hantei[tmp] = true;
					tmp = ik*j;
					j++;
				}
			} else if(iv >= 1){
				int j = 2;
				int tmp = ik*j;
				while(tmp <= 1000000){
					hantei[tmp] = true;
					j++;
					tmp = ik*j;
				}
			}
		}

		int ans = 0;
		for(int a: as){
			if(!hantei[a]) ans++;
		}
		System.out.println(ans);

	}
}


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

int main() {
  int64_t a,b,n;
  cin>>n>>a>>b;
  int64_t c=a+b;
  int64_t d=n/c;
  int64_t e=n%c;
  int64_t bl;
  if(e<a){
    bl=a*d+e;
  }else{
    bl=a*d+a;
  }
  cout<<bl<<endl;
}

Measured memory_bytes: 256
N, Y = map(int, input().split())
flag = False
for a in range(N + 1):
  for b in range(N - a + 1):
    c = N - a - b
    if a * 10000 + b * 5000 + c * 1000 == Y:
      flag = True
      break
  if flag:
    break
if flag:
  print("{} {} {}".format(a, b, c))
else:
  print("-1 -1 -1")

Measured memory_bytes: 40684
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define INF 1000000000000000000
#define all(x) x.begin(), x.end()

int main() {
    int N, W;
    cin >> N >> W;
    ll V = pow(10, 5);
    vector<vector<ll>> dp(N + 10, vector<ll>(V + 10, INF));
    vector<ll> weight(N);
    vector<ll> value(N);
    rep(i, N) { cin >> weight[i] >> value[i]; }

    dp[0][0] = 0;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= V; j++) {
            if (j >= value[i])
                dp[i + 1][j] = min(dp[i][j - value[i]] + weight[i], dp[i][j]);
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j]);
        }
    }

    ll res = 0;
    rep(i, N + 1) {
        rep(j, V + 1) {
            if (W >= dp[i][j]) {
                res = max(res, (ll)j);
            }
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 87296
N, Q = map(int, input().split())
S = input()
items = []
for i in range(Q):
    items.append(tuple(map(int, input().split())))

acc = [0] * N
for i in range(1, N):
    if S[i] == "C" and S[i-1] == "A":
        acc[i] += 1
from itertools import accumulate
acc = list(accumulate(acc))

for l, r in items:
    print(acc[r-1]-acc[l-1])


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

int main(){
    int n;
    long long a,ans = 0;

    cin >> n;
    map<long long,long long> up,down;
    for(int i = 1;i <= n;i++){
        cin >> a;
        if(i + a <= n)up[i + a]++;
        if(0 <=i - a)down[i - a]++;
    }
    for(pair<long long,long long> up_num : up){
        int down_num = down[up_num.first];
        ans += (up_num.second * down_num);
    }
    cout << ans <<endl;
}


Measured memory_bytes: 22428
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
res = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    res[p - 1] += x
s = [0]
d = [True] * n
while s:
    p = s.pop()
    d[p] = False
    for node in g[p]:
        if d[node]:
            res[node] += res[p]
            s.append(node)
print(' '.join(map(str, res)))


Measured memory_bytes: 129064
/*
* @Author: kabbo
* @Date:   2020-06-21 21:00:55
* @Last Modified by:   kabbo
* @Last Modified time: 2020-06-21 21:03:27
*/
#include<bits/stdc++.h>
using namespace std;
#define pii pair<long long,long long>
#define endl '\n'
#define ull unsigned long long
#define ll long long
const int mod = 1e9 + 7;
using u64 = uint64_t;
using u128 = __uint128_t;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
	char ch;
	cin >> ch;
	if (isupper(ch)) {
		cout << "A" << endl;
	}
	else
		cout << "a" << endl;
}
int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	/*int t;
	cin >> t;
	for (int i(1); i <= t; ++i) {
		printf("Case %d: ", i);*/
	solve();
	//}
#ifndef LOCAL_DEFINE
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
#endif
	return 0;
}

Measured memory_bytes: 3828
n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(a)
tempcost = ans
xt = 0
bc = a
for i in range(1, n):
    xt += x
    a = [a[-1]] + a[0:-1]
    bc = [v if v < bc[i] else bc[i] for (i, v) in enumerate(a)]
    tempcost = xt + sum(bc)
    ans = min(ans, tempcost)
print(ans)

Measured memory_bytes: 3188
import java.util.*;

public class Main{ 
  
  public static void main(String[] args) throws Exception{
    
    Scanner sc = new Scanner(System.in);
    
    int[] math = new int[9];
    for(int i = 0; i < 9; ++i){
      math[i] = sc.nextInt();
    }
    
    int a = math[1]-math[0];
    int b = math[4]-math[3];
    int c = math[7]-math[6];
    
    int d = math[2]-math[0];
    int e = math[5]-math[3];
    int f = math[8]-math[6];
    
    int g = math[3]-math[0];
    int h = math[4]-math[1];
    int i = math[5]-math[2];
      
    int j = math[6]-math[0];
    int k = math[7]-math[1];
    int l = math[8]-math[2];
      
    
    if((a == b && b == c && c ==a)
        && (d == e && e == f && f ==d)
        && (g == h && h == i && i ==g)
        && (j == k && k == l && l ==j)){
      System.out.println("Yes");
    }else{
       System.out.println("No");
    } 
  }
} 


Measured memory_bytes: 35696
using System;

public class Hello
{
    public static void Main()
    {
        string line;
        for (; (line = Console.ReadLine()) != null;)
        {
            var n = int.Parse(line.Trim());
            var c = 1;
            int up;  int down;
            while (true)
            {
                if (IsPrime(n + c)) { up = n + c; break; }
                else c++;
            }
            c = 1;
            while (true)
            {
                if (IsPrime(n - c)) { down =  n -c; break; }
                else c++;
            }
            Console.WriteLine("{0} {1}", down, up);
        }
    }
    public static bool IsPrime(int n)
    {
        if (n < 2) return false;
        else if (n == 2) return true;
        else if (n % 2 == 0) return false; 
        double sqrtNum = Math.Sqrt(n);
        for (int i = 3; i <= sqrtNum; i += 2)
            if (n % i == 0) return false;
        return true;
    }
}

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

#define cn count
#define pb push_back
#define in insert
#define fs first
#define sc second
#define sz size
#define len length
#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define forni(i, n) for (ll i = 1; i < (ll) (n); ++i)
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;
using ll = long long;
const ll inf = 1e9+7; 
const double PI =  3.141592653589793;

int main(){
	IO;
	ll n,a,prev,cnt=0,maxi=0;
	cin>>n;
	forn(i,n){
		cin>>a;
		if(i==0)prev=a;
		else if(prev>=a) {cnt++;}
		else{
			maxi = max(maxi,cnt);
			cnt = 0;
		}
		prev = a;
	}
	maxi = max(maxi,cnt);
	cout<<maxi<<"\n";
	return 0;
}


// _   .-')                .-. .-')                 .-')                                               
//( '.( OO )_              \  ( OO )               ( OO ).                                             
// ,--.   ,--.).-'),-----. ,--. ,--.  .-'),-----. (_)---\_) ,--. ,--.     .-----.  ,-.-')  .-'),-----. 
// |   `.'   |( OO'  .-.  '|  .'   / ( OO'  .-.  '/    _ |  |  | |  |    '  .--./  |  |OO)( OO'  .-.  '
// |         |/   |  | |  ||      /, /   |  | |  |\  :` `.  |  | | .-')  |  |('-.  |  |  \/   |  | |  |
// |  |'.'|  |\_) |  |\|  ||     ' _)\_) |  |\|  | '..`''.) |  |_|( OO )/_) |OO  ) |  |(_/\_) |  |\|  |
// |  |   |  |  \ |  | |  ||  .   \    \ |  | |  |.-._)   \ |  | | `-' /||  |`-'| ,|  |_.'  \ |  | |  |
// |  |   |  |   `'  '-'  '|  |\   \    `'  '-'  '\       /('  '-'(_.-'(_'  '--'\(_|  |      `'  '-'  '
// """    """     """""""" """  """"      """""""  """""""  """"""""      """"""   """         """""""



Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii  = pair<int,int>;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define MOD 1000000007
#define EPS 10e-8
int gcd(int a,int b){return b?gcd(b,a%b):a;}    //最大公約数
int lcm(int a, int b) {return a * b / gcd(a, b);}   //最小公倍数
uintmax_t combination(unsigned int n, unsigned int r){    //組み合わせ
    if ( r * 2 > n ) r = n - r;
    uintmax_t dividend = 1;
    uintmax_t divisor  = 1;
    for ( unsigned int i = 1; i <= r; ++i ) {
        dividend *= (n-i+1);
        divisor  *= i;
    }
    return dividend / divisor;
}

int main()
{
    string s;
    cin >> s;
    bool key = true;
    int count=0;
    while (key)
    {
        key = false;
        rep(i, (int)s.length())
        {
            if(s[i]=='1'){
                count++;
            }
        }
    }
    cout << 2*min(count,(int)s.length()-count) << endl;
    return 0;
}

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

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	string s;
	cin >> s;
	int num[26] = {};
	for(char x : s)
		num[x-'a']++;

	int ans = 100;
	for(int i = 0; i < 26; i++){
		if(num[i] == 0) continue;
		string now = s;
		int j;
		for(j = 0;; j++){
			bool check = true;
			for(int k = 1; k < (int)now.size(); k++)
				if(now[k] != now[k-1])
					check = false;
			if(check) break;

			string next;
			for(int k = 0; k < (int)now.size()-1; k++){
				if(now[k] == i + 'a' || now[k+1] == i + 'a')
					next += i + 'a';
				else
					next += now[k];
			}
			now = next;
		}
		ans = min(ans, j);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s, t;
    cin >> s >> t;
    //int dp[s.length() + 1][t.length() + 1];
    vector<vector<int>> dp(s.length() + 1, vector<int>(t.length() + 1, 0));
   // for (int i = 0; i <= s.length(); i++) for (int j = 0; j<= t.length(); j++) dp[i][j] = 0;
    for (int i = 0; i < s.length(); i++)
        for (int j = 0; j < t.length(); j++){
            if (s[i] == t[j]) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
            dp[i + 1][j + 1] = max(max(dp[i+1][j+1], dp[i][j+1]), dp[i+1][j]);
        }
    string ans = "";
    //cout << dp[s.length()][t.length()] << endl;
    int i = s.length(), j = t.length();
    while (i > 0 && j > 0){
        if (s[i - 1] == t[j - 1]){
            i--;
            j--;
            ans = s[i] + ans;
        } else if (dp[i-1][j] > dp[i][j-1]){
            i--;
        } else j--;
    }
    cout << ans;
}


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


int main() {

    int n;
    cin >> n;
    vector<int> d(n);
    rep(i,n) cin >> d[i];
    sort(d.begin(), d.end());

    cout << d[n/2] - d[n/2-1] << endl;
}

Measured memory_bytes: 768
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		while (true) {
			String str = sc.nextLine();
			if (str.equals("END OF INPUT")) break;
			String[] strs = str.split(" ");
			for (int i = 0; i < strs.length; i++) {
				out.print(strs[i].length());
			}
			out.println();
		}
		out.flush();
		sc.close();
	}
}	

Measured memory_bytes: 25928
#include <iostream>
#include <utility>
#include <string>
#include <vector>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)

int main()
{
  int n, m;
  while(cin >> n >> m, (n|m)) {
    int t[n];
    int ts = 0;
    int h[m];
    int hs = 0;

    rep(i, n) {
      cin >> t[i];
      ts += t[i];
    }
    rep(i, m) {
      cin >> h[i];
      hs += h[i];
    }

    int min = 1 << 29;
    int ta = 0;
    int ha = 0;
    rep(i, n) {
      rep(j, m) {
        if( ts - t[i] + h[j] == hs - h[j] + t[i] ) {
          if( min > t[i] + h[j] ) {
            min = t[i] + h[j];
            ta = t[i];
            ha = h[j];
          }
        }
      }
    }

    if( min == 1 << 29 ) {
      cout << "-1" << endl;
    } else {
      cout << ta << " " << ha << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 1160
n, *a = map(int, open(0).read().split())

l = r = 0
s = 0
xor = 0
unko = 0
while l < n:
    while r < n and s + a[r] == xor ^ a[r]:
        s += a[r]
        xor ^= a[r]
        r += 1
    unko += r - l
    s -= a[l]
    xor ^= a[l]
    if l == r:
        r += 1
    l += 1
print(unko)


Measured memory_bytes: 31472
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()


int main()
{
    ll x, y;cin>>x>>y;
    int ans = 1;
    while(x*2<=y){
        ++ans;
        x*=2;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define EPS      (double)1e-9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;
template<class Type> void line(const Type &a){int cnt=0;for(const auto &elem:a){if(cnt++)cerr<<' ';cerr<<elem;}cerr<<endl;}

template<class Type_a,class Type_b> bool chmax(Type_a &a,const Type_b &b){if(a<b){a=b;return true;}return false;}
template<class Type_a,class Type_b> bool chmin(Type_a &a,const Type_b &b){if(a>b){a=b;return true;}return false;}

template<class Type_k,class Type_p>
Type_p mod_pow(long long n,Type_k k,Type_p p){//n^k(mod p).
	if(k==0) return 1;
	long long res=mod_pow(n*n%p,k/2,p);
	if(k&1) res=res*n%p;
	return res;
}

/*素因数分解*/
template<class Type>
map<Type,int> prime_factor(Type n){
	map<Type,int> res;//自然数nの約数firstがsecond個ある.
	for(Type i=2;i*i<=n;++i){
		while(n%i==0){
			res[i]++;
			n/=i;
		}
	}
	if(n!=1) res[n]=1;
	return res;
}

//解説参考.
int main(){
	int n;
	cin>>n;
	
	vi a(n);
	REP(i,n) cin>>a[i];
	
	map<int,int> mp;
	REP(i,n){
		map<int,int> res=prime_factor(a[i]);
		for(auto elem:res) chmax(mp[elem.first],elem.second);
	}
	
	llong ln=1LL;
	for(auto elem:mp) ln=ln*mod_pow(elem.first,elem.second,MOD)%MOD;
	
	llong ans=0LL;
	REP(i,n){
		llong b=ln*mod_pow(a[i],MOD-2,MOD)%MOD;
		ans=(ans+b)%MOD;
	}
	
	cout<<ans<<endl;
}

Measured memory_bytes: 4128
N, M, K = map(int, input().split(' '))
A_ls = [0] + list(map(int, input().split(' ')))
for i in range(len(A_ls) - 1):
    A_ls[i + 1] += A_ls[i]

B_ls = [0] + list(map(int, input().split(' ')))
for i in range(len(B_ls) - 1):
    B_ls[i + 1] += B_ls[i]

b_cnt,result = M, 0
for a_cnt in range(N + 1):
    if A_ls[a_cnt] > K:
        break
    while A_ls[a_cnt] + B_ls[b_cnt] > K:
        b_cnt -= 1
    result = max(result, a_cnt + b_cnt)
print(result)

Measured memory_bytes: 43196
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,0,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
using namespace std;

int main(){
  int A,B;
  cin>>A>>B;
  string S;
  cin>>S;
  bool CAN=true;
  
  REP(i,S.size()){
    if(i==A){
      if(S.at(i)!='-') CAN=false;
    }
    else{
      if(S.at(i)=='-') CAN=false;
    }
  }
  
  if(CAN) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <numeric>
#include <bitset>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
using namespace std;

typedef long long ll;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
bool ISINT(double x){return fabs(x-(int)x)<EPS;}
bool ISEQ(double x,double y){return fabs(x-y)<EPS;}
string itos(ll x){stringstream ss;ss<<x;return ss.str();}
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define EREP(i,a,b) for(int i=a;i<=b;i++)
#define erep(i,n) EREP(i,0,n)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

#define INF 999999

typedef complex<double> P;

int n;
P t[102];
bool flg[5000];

double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}

P crosspoint(P a,P b,P c,P d){
  double A = cross(b - a, d - c);
  double B = cross(b - a, b - c);
  if (abs(A) < EPS && abs(B) < EPS) return c; // same line
  if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
  return c + B / A * (d - c);
}

vector<double> getCrossPoint(double y){
  vector<double> v;

  rep(i,n){
    if(t[i].imag() < y && y < t[(i+1)%n].imag() ||
       t[(i+1)%n].imag() < y && y < t[i].imag()){
      P p = crosspoint(P(-INF,y),P(INF,y),t[i],t[(i+1)%n]);
      v.push_back(p.real());
    }
  }
  sort(v.begin(),v.end());

  return v;
}

int main(void){
  while(scanf("%d",&n),n){
    int hy = -INF, ly = INF;

    rep(i,n){
      scanf("%lf%lf",&t[i].real(),&t[i].imag());
      t[i].real() += 2000;
      t[i].imag() += 2000;
      hy = max(hy,(int)t[i].imag());
      ly = min(ly,(int)t[i].imag());
    }

    int res = 0;
    REP(i,ly,hy){
      memset(flg,0,sizeof(flg));
      vector<double> v1 = getCrossPoint(i+EPS);
      vector<double> v2 = getCrossPoint(i+1-EPS);

      for(int i=0;i<v1.size();i+=2){
        int from = floor(min(v1[i],v2[i]));
        int to = ceil(max(v1[i+1],v2[i+1]));
        for(int j=from;j<to;j++){
          if(!flg[j]){
            res++;
            flg[j] = true;
          }
        }
      }
    }
    printf("%d\n",res);
  }
}

Measured memory_bytes: 972
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> val(N, 0);
    vector<int> cost(N, 0);
    for (int i = 0; i < N; ++i)
        cin >> val[i];
    for (int i = 0; i < N; ++i)
        cin >> cost[i];
    for (int i = 0; i < N; ++i)
        val[i] = val[i] - cost[i];

    sort(val.begin(), val.end());
    int sum = 0;
    for (int i = N-1; i >= 0; --i)
    {
        if (val[i] > 0)
            sum += val[i];
        else
            break;
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#入力
n, d = map(int, input().split())
point = [[int(i) for i in input().split()] for j in range(n)]
#点1から計算する
m = 0
for i in range(n):
	for j in range(i+1,n):
		a = 0
		for k in range(d):
			a += (point[i][k]-point[j][k])**2
		b = a**(1/2)
		if b.is_integer():
			m += 1
print(m)

Measured memory_bytes: 3316
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

#define INF 1000000007 //1000000000000000003
#define MOD 1000000007
#define MAX 2000005

#define ll long long

//printf("%.10f", );
//cout << fixed << setprecision(10) << heikin << endl;
//vector<vector<int>> data(3, vector<int>(4, -1));
//left + 1 < top

using namespace std;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using edge = struct { int to; long long dist; };
const double PI = 3.141592653589793;
long long fact[MAX], inv[MAX];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

//////////////////////////////////

vector<vector<int>> tree(100005);
int color[100005];
map<P, int>colorMap;
int m = 0;

struct BridgeInfo {
	int town1;
	int town2;
	int year;
	BridgeInfo(int t1, int t2, int y) {
		town1 = t1;
		town2 = t2;
		year = y;
	}
};

struct People {
	int index;
	int town;
	int year;
	People(int i, int t, int y) {
		index = i;
		town = t;
		year = y;
	}
};

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

struct UnionFind {
	vector<int>uf;
	
	UnionFind(int size) :uf(size, -1) {};

	int root(int target) {
		if (uf[target] < 0)return target;
		else return uf[target] = root(uf[target]);
	}

	void merge(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b)return;
		if (uf[b] < uf[a])swap(a, b);
		uf[a] += uf[b];
		uf[b] = a;
	}
};

ll CalcPow(ll num, ll power) {
	if (power == 0)return 1;
	if (power % 2 == 0) {
		ll half = CalcPow(num, power / 2);
		return (half * half) % MOD;
	}
	else return (num * CalcPow(num, power - 1)) % MOD;
}

ll combination(ll all, ll select) {
	if (all < select) return 0;
	if (all < 0 || select < 0) return 0;
	return fact[all] * (inv[select] * inv[all - select] % MOD) % MOD;
}

void initCombination(int max) {
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= max; ++i) {
		fact[i] = fact[i-1] * i % MOD;
	}

	inv[max] = CalcPow(fact[max], MOD - 2);
	for (int i = max - 1; 0 <= i; --i) {
		inv[i] = (inv[i + 1] * (i + 1)) % MOD;
	}
}

void dfs(int from) {
	int c = 1;
	for (auto t : tree[from]) {
		c = c != color[from] ? c : c + 1;
		color[t] = c;
		colorMap[make_pair(from, t)] = c;
		m = max(c, m);
		dfs(t);
		c++;
	}
}

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

	vector<vector<ll>> data(10, vector<ll>(10, 0));
	for (int i = 1; i <= N; ++i) {
		int keta = log10(i);
		int first = i / pow(10, keta);
		int last = i % 10;
		data[first][last]++;
	}

	ll ans = 0;
	for (int i = 1; i <= 9; ++i) {
		for (int j = 1; j <= 9; ++j) {
			ans += (data[i][j] * data[j][i]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 2560
/********************************************************************************
	
	Code by a weak man who named CYJian, and he hopes the code can get more points.

	Algorithm: 

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//{{{ FAST IO AND SOME FUNCTIONS
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
	char ch, t = 0; x = 0;
	while(!isdigit(ch = ge)) t |= ch == '-';
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }

template<typename T> inline void chkmin(T&a, T b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }
//}}}

const int mod = 1e9 + 7;

inline int Mod(int x) { return x >= mod ? x - mod : x; }
inline void Add(int &x, int y) { x += y, x -= x >= mod ? mod : 0; }

int f[5010];
int g[5010];
int P[5010];
int M[5010];
int F[2][5010];

int main() {
#ifdef LOCAL
	FILE("");
#endif

	int n = ri, A = ri, B = ri, res = 1;
	for(int i = 1; i <= n; i++) res = Mod(res << 1);
	if(A == 1 || B == 1) return printf("%d\n", res), 0;
	if(A > B) swap(A, B);
	f[0] = 1, g[0] = 1;
	for(int i = A; i < B; i++) {
		f[i] = Mod(f[i - 1] + g[i - 1]);
		for(int j = A; j <= i; j++)
			Add(g[i], f[i - j]);
	}

	for(int i = 1; i < B; i++)
		for(int j = 1; j <= i; j++)
			P[i] = (P[i] + 1LL * g[i - j] * (i == j ? 1 : j)) % mod;
	for(int i = 1; i < B; i++)
		for(int j = 1; j <= i; j++)
			M[i] = (M[i] + 1LL * g[i - j] * (i == j ? 1 : j - 1)) % mod;

	F[0][0] = F[1][0] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j < B; j++) {
			if(i == j || i == n) {
				F[1][i] = (F[1][i] + 1LL * F[0][i - j] * P[j]) % mod;
				if(i == j) break;
			} else F[1][i] = (F[1][i] + 1LL * F[0][i - j] * M[j]) % mod;
		}
		for(int j = 1; j < A; j++) {
			Add(F[0][i], F[1][i - j]);
			if(i == j) break;
		}
	}

	cout << Mod(res + mod - Mod(F[0][n] + F[1][n])) << endl;
	return 0;
}

Measured memory_bytes: 3772
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

struct before_main{before_main(){cin.tie(0); ios::sync_with_stdio(false);}} before_main;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

int main() {

  int N; cin >> N;

  vector<int> g[1001];
  vector<string> msg(1001);

  rep(i, N) {
    int k; string m; cin >> k >> m;
    g[k].emplace_back(i+1);
    msg[i+1] = m;
  }

  std::function<void(int, int)> dfs = [&](int idx, int depth) {
    if(depth + 1) {
      rep(i, depth) cout << '.';
      cout << msg[idx] << endl;
    }
    rep(i, g[idx].size()) {
      dfs(g[idx][i], depth + 1);
    }
  };

  dfs(0, -1);
  
  return 0;
}

Measured memory_bytes: 3448
#include <stdio.h>
#include <math.h>

#define EPS 1e-11

typedef struct
{
	double x;
	double y;
	double r;
} Circle;

int main(void)
{
	int n;
	
	scanf("%d", &n);
	while (n-- > 0){
		Circle a;
		Circle b;
		double xdif, ydif, d;
		double sr, dr;
		
		scanf("%lf %lf %lf", &a.x, &a.y, &a.r);
		scanf("%lf %lf %lf", &b.x, &b.y, &b.r);
		xdif = a.x - b.x;
		ydif = a.y - b.y;
		d = xdif * xdif + ydif * ydif;
		sr = (a.r + b.r) * (a.r + b.r);
		dr = (a.r - b.r) * (a.r - b.r);
		
		//printf("%Lf %Lf %Lf\n", d, sr, dr);
		if (d > sr){
			puts("0");
		}
		else {
			if (d == sr || d >= dr){
				puts("1");
			}
			else if (a.r > b.r){
				puts("2");
			}
			else {
				puts("-2");
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 616
#include<iostream>

using namespace std;

int main(void) {
  char s[5];
  cin >> s;
  bool a = false, b = false;
  if ((s[0] == '0' && s[1] == '0') || (s[0] == '1' && s[1] >= '3') || s[0] > '1') {
    a = true;
  }
  if ((s[2] == '0' && s[3] == '0') || (s[2] == '1' && s[3] >= '3') || s[2] > '1') {
    b = true;
  }

  if (a && b) {
    cout << "NA" << endl;
  } else if (a) {
    cout << "YYMM" << endl;
  } else if (b) {
    cout << "MMYY" << endl;
  } else {
    cout << "AMBIGUOUS" << endl;
  }

  return 0;
}

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

bool IsPrime(int n) {
	for(int i = 2; i*i <= n; i++) {
		if(n % i == 0) {
		    return false;
		}
	}
	return true;
}

int main(void){
   int count=0, n;
   cin >> n;
   for(int i = 0; i < n; i++) {
       int p;
       cin >> p;
       if(IsPrime(p)) {
         count++;
       }
   }
   cout << count << endl;
   return 0;
}


Measured memory_bytes: 3068
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << 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...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 1e5 + 10;
const int M = 13;
char s[N];
int dp[N][M];

void add(int& x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}

int main() {
  scanf("%s", s);
  int n = strlen(s);
  // trace(n);
  dp[0][0] = 1;
  for (int i = 0; i < n; ++i) {
    if (s[i] != '?') {
      int x = s[i] - '0';
      for (int j = 0; j < M; ++j) {
        add(dp[i + 1][(j * 10 + x) % M], dp[i][j]);
      }
    } else {
      for (int j = 0; j < M; ++j) {
        for (int k = 0; k < 10; ++k) {
          add(dp[i + 1][(j * 10 + k) % M], dp[i][j]);
        }
      }
    }
    // for (int j = 0; j < M; ++j) {
    //   trace(i + 1, j, dp[i + 1][j]);
    // }
  }
  printf("%d\n", dp[n][5]);
  return 0;
}


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

using namespace std;

int main()
{
  int A, B;
  cin >> A >> B;

  int num = 0;
  while(1)
  {
    if (B <= A * num - (num - 1))
    {
      cout << num << endl;
      return 0;
    }
    ++num;
  }
}


Measured memory_bytes: 256
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def ris(): return list(input())
def pli(): return "".join(list(map(str, ans)))

N = ri()
K = ri()
X = ri()
Y = ri()

if(K >= N):
    print(X*N)
else:
    print(K*X+(N-K)*Y)

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

int main()
{
	int n,x;
	int flag=1;
	cin>>n;
	vector<int> a;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		a.push_back(x);
	}
	for(auto v:a)
	{
		if((v%2==0) && ((v%3!=0)&&(v%5!=0)))
		{
			flag=0;
			break;
		}
		
	}
	if(flag==0)
	{
		cout<<"DENIED";
	}
	else
	{
		cout<<"APPROVED";
	}
	return 0;
}


Measured memory_bytes: 256
#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() {
  int m = 2019;
  string s;
  cin >> s;
  int n = s.size();
  reverse(s.begin(), s.end());

  // 余りをカウントする
  vector<int> cnt(m, 0);
  cnt.at(0) = 1;
  int x = 1, tot = 0;
  ll ans = 0;
  rep(i, n) {
    tot += (s.at(i) - '0') * x;
    tot %= m;
    ans += cnt.at(tot);
    cnt.at(tot)++;
    x = x * 10 % m;
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3732
#include <stdio.h>
int main(void)
{
  int a, b, c, p;
  scanf("%d %d %d", &a, &b, &c);
  
  if((a==b) && (b==c) && (c==a))
    p = 1;
  else if((a==b) || (b==c) || (c==a))
    p = 2;
  else
    p = 3;
  
  printf("%d", p);
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long,long long>
 
int main() {
	ll n,ans=0,z=1;
	cin>>n;
	if(n%2!=0){
		cout<<0;
		return 0;
	}
	while(z<=n){
		ans+=n/(10*z);
		z*=5;
	}
	cout<<ans;
	return 0;
}

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

int main(){
	while(1){
		int n;
		cin >> n;
		if(n==0)break;
	
		char c[100];
		for(int i=0;i<n;i++){
			cin >> c[i];
		}

		int cnt[26] = {0};
		
		for(int i=0;i<n;i++){
			cnt[(int)(c[i]-'A')]++;

			int max1 = -1;
			int max2 = -1;

			for(int j=0;j<26;j++){
				if(cnt[j]>max1){
					max2 = max1;
					max1 = cnt[j];
				}else if(cnt[j]>max2){
					max2 = cnt[j];
				}
			}

			if(max1-max2>n-(i+1)){
				for(int j=0;j<26;j++){
					if(cnt[j]==max1){
						cout << (char)(j+'A') << ' ';
						break;
					}
				}
				cout << (i+1) << endl;
				break;
			}
			
			if(i==n-1){
				cout << "TIE" << endl;		
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define int long long
#define debug(x) cerr << "\n" \
                      << #x << ": " << x << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define INF (1LL << 30)
#define pii pair<int, int>
#define MOD 1000000007
using namespace std;


signed main()
{
    int N,K;
    string S;
    cin>>N>>K;
    cin>>S;

    S[K-1] -= ('A' - 'a');

    cout<<S<<endl;

    return 0;
}

Measured memory_bytes: 256
def a():return input()#s
def ai():return int(input())#a,n or k
def ma():return map(int, input().split())#a,b,c,d or n,k
def ms():return map(str, input().split())#,a,b,c,d
def lma():return list(map(int, input().split()))#x or y
def lms():return list(map(str, input().split()))#x or y
a = ai()
z = lma()
y = lma()
x = [z,y]
k = []
l = 0
s = 0
sm = 0
M = 0
for j in range(a):
    l = 0
    sm = 0
    for i in range(a):
        sm+= x[l][i]
        if s == i:
            l+=1
            #print(l,i,j)
            sm+= x[l][i]
    s+=1
    M = max(M,sm)
print(M)
        

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
//bit全探索
int main() {
  int N;
  cin >> N;
  vector<vector<int>> open(N,vector<int>(10));
  for(int i=0; i<N; i++){
    for(int j=0; j<10; j++){
      cin >> open.at(i).at(j);
    }
  }
  vector<vector<int>> benefit(N,vector<int>(11));
  for(int i=0; i<N; i++){
    for(int j=0; j<11; j++){
      cin >> benefit.at(i).at(j);
    }
  }
  
  int64_t joisino = -10000000000;
  for(int bit = 0; bit < (1 << 10); bit++){
    map<int,bool> mp;
    for(int i=0; i<10; i++){
      if(bit & (1 << i)){
        mp[i] = true;
      }
    }
    if(mp.size() != 0){
      int64_t bene_x = 0;
      for(int j=0; j<N; j++){
        int cnt = 0;
        for(int k=0; k<10; k++){
          if(open.at(j).at(k) == 1 && mp.count(k)){
            cnt++;
          }
        }
        bene_x += benefit.at(j).at(cnt);
      }
      joisino = max(joisino,bene_x);
    }
  }
  cout << joisino << endl;
}

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


int n,l;
char d[200];
int p[200];

int main(){
  while(1){
    cin>>n>>l;
    if(n==0&&l==0)break;
    int maxm=0,id=0;
    for(int i=0;i<n;i++){
      cin>>d[i]>>p[i];
      int a=p[i];
      if(d[i]=='R')a=l-a;
      if(a==maxm&&d[i]=='L'){
	id=i;
      }else if(a>maxm){
	maxm=a;
	id=i;
      }
    }
    
    vector<int> vec;
    int cnt=0;
    
    if(d[id]=='L'){
      for(int i=id;i>=0;i--){
	int e=abs(p[id]-p[i]);
	if(e%2==1)continue;
	if(d[i]=='R')cnt++;
	vec.push_back(i);
      }
    }else{
      for(int i=id;i<n;i++){
	int e=abs(p[id]-p[i]);
	if(e%2==1)continue;
	if(d[i]=='L')cnt++;
	vec.push_back(i);
      }
    }
    cout<<maxm<<' '<<vec[cnt]+1<<endl;
  }
  return 0;
}

Measured memory_bytes: 1216
#include<stdio.h>
int main(void)
{
	
	int  a, b, x, c;
	scanf("%d", &a);
	scanf("%d", &b);
	x = 10 * b;
	c = 12.5 * a;
	while (x < 10 * (b + 1))
		{
			for (c = 12.5 * a+0.5; c < 12.5 * (a + 1); c++)
			{
				if (c == x)
				{
					printf("%d", x);
					return 0;
				}
			}
			x++;
		}
		printf("%d", -1);
		return 0;
}


Measured memory_bytes: 128
import sys
sin = sys.stdin.readlines()
N, M, Q = map(int, sin[0].split())

LR = [[0 for _ in range(N+2-i)] for i in range(N+2)]
for line in sin[1:M+1]:
  L, R = map(int, line.split())
  LR[L][R-L+1] += 1

for i in range(2,N+2):
  for j in range(1,N-i+2):
    LR[j][i] += LR[j][i-1] + LR[j+1][i-1] - LR[j+1][i-2]
 
for line in sin[M+1:]:
  p, q = map(int, line.split())
  print(LR[p][q-p+1])


Measured memory_bytes: 29996
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const ll MOD2=998244353;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
  ll n;
  cin >> n;
  ll ans=INF;
  FOR(i,1,n){
    ll a=i,b=n-i;
    ll cnt=0;
    while(a!=0){
      cnt+=a%10;
      a/=10;
    }
    while(b!=0){
      cnt+=b%10;
      b/=10;
    }
    ans=min(ans,cnt);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import Control.Monad
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as B
import Data.Char

main :: IO ()
main = do
    s <- getLine :: IO String
    putStrLn $ if head s == 'A'
        && 1 == length (filter (=='C') (drop 1 (reverse (drop 2 s)))) 
        && all isLower (filter (/='C') (tail s))
        then "AC"
        else "WA"

Measured memory_bytes: 380
#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>;

const int MOD = 1e9 + 7;

int main() {
  int n;
  string s1, s2;
  cin >> n >> s1 >> s2;
  int ans = 3;
  int si = 1;
  if (s1[0] != s2[0]) {
    si = 2;
    ans = 6;
  }
  for (int i = si; i < n; ++i) {
    if (s1[i] == s2[i]) {
      if (s1[i-1] == s2[i-1]) ans = ans * 2 % MOD;
    } else {
      if (s1[i-1] == s1[i]) {
        if (s1[i-2] == s2[i-2]) ans = ans * 2 % MOD;
        else ans = (ll)ans * 3 % MOD;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3624
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

long long powmod(lint a,lint b){
  return b?powmod(a*a%MOD,b/2)*(b%2?a:1)%MOD:1;
}

lint LCM(lint a,lint b){
  if(a==0 || b==0) return 0;
  lint tmp,r,x;
  x=a*b;
  if(a<b) tmp=a,a=b,b=tmp;
  r=a%b;
  while(r!=0) a=b,b=r,r=a%b;
  x=x/b;
  return x;
}

lint GCD(lint a,lint b){
  if(a==0 || b==0) return max(a,b);
  else return (a*b)/LCM(a,b);
}

multiset<lint> decomp(lint N){
    multiset<lint> res;
    for(int i=2;i<=1000;i++){
        while(N%i==0) N/=i,res.insert(i);
        if(N==1) break;
        if(i==1000) res.insert(N);
    }
    return res; 
}

lint save[1100000]={};

int main(void){
    int N;
    cin >> N;
    lint A[N];
    lint ans=0;
    lint mul=1;
    lint div=1;
    rep(i,N) cin >> A[i];
    rep(i,N) mul=(mul*A[i])%MOD;
    rep(i,N){
        multiset<lint> muls=decomp(A[i]);
        multiset<lint> acum;
        while(!muls.empty()){
            auto itr=muls.begin();
            if(save[*itr]>=1) div=(div*(*itr))%MOD,save[*itr]--;
            acum.insert(*itr);
            muls.erase(itr);
        }
        while(!acum.empty()){
            auto it=acum.begin();
            save[*it]++;
            acum.erase(it);
        }
    }
    mul=(mul*powmod(div,MOD-2))%MOD;
    rep(i,N) ans=(ans+mul*powmod(A[i],MOD-2))%MOD;
    cout << ans << endl;
}

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

struct dice{
  int u;
  int s;
  int e;
  int w;
  int n;
  int d;
};

int num;
dice move(dice, char);
bool judge(dice, dice);


int main(){
  cin>>num;
  dice dices[100];
  for(int i=0; i<num; i++){
    cin>>dices[i].u>>dices[i].s>>dices[i].e>>dices[i].w>>dices[i].n>>dices[i].d;
  }

  for(int h=0; h<num; h++){
    for(int i=h+1; i<num; i++){
      dice temp = dices[i];
      bool solved = false;
      for(int j=0; j<4; j++){
	if(judge(dices[h],temp)){cout<<"No"<<endl;solved = true; return 0;}
	temp = move(temp,'E');
	for(int k=0; k<4; k++){
	  temp = move(temp,'N');
	  if(judge(dices[h],temp)){cout<<"No"<<endl;solved = true; return 0;}
	  for(int l=0; l<4; l++){
	    temp = move(temp,'R');
	    if(judge(dices[h],temp)){cout<<"No"<<endl;solved = true; return 0;}
	  }
	}
      } 
    }
  }
  cout<<"Yes"<<endl;
}

bool judge(dice dice1, dice dice2){
  //cout<<dice1.u<<dice1.s<<dice1.e<<dice1.w<<dice1.n<<dice1.d<<endl;
  if(dice1.u == dice2.u &&dice1.s == dice2.s &&dice1.e == dice2.e &&dice1.w == dice2.w &&dice1.n == dice2.n &&dice1.d == dice2.d){
    return true;
  }
  return false;
}

dice move(dice dice1, char c){
    dice temp = dice1;
    if(c=='E'){     
      dice1.d = temp.e;
      dice1.w = temp.d;
      dice1.u = temp.w;
      dice1.e = temp.u;
    }else if(c=='N'){
      dice1.n = temp.u;
      dice1.u = temp.s;
      dice1.s = temp.d;
      dice1.d = temp.n;
    }else if(c=='S'){
      dice1.n = temp.d;
      dice1.u = temp.n;
      dice1.s = temp.u;
      dice1.d = temp.s;
    }else if(c=='W'){
      dice1.u = temp.e;
      dice1.w = temp.u;
      dice1.d = temp.w;
      dice1.e = temp.d;
    }else if(c=='R'){
      dice1.s = temp.w;
      dice1.w = temp.n;
      dice1.n = temp.e;
      dice1.e = temp.s;
    }
    return dice1;
}




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

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

    int N;
    cin >> N;
    vector<int> A(N);
    int tmp;
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        A[i] = tmp;
    }

    tmp = A[0];
    for (int i : A) {
        tmp = __gcd(tmp, i);
    }

    cout << tmp << "\n";
    return 0;
}

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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

string dp[10050];

ll compare(string s1, string s2) {
  if (s1.size() > s2.size()) {
    return 1;
  }

  if (s1 > s2) {
    return 1;
  }

  // for (ll i = 0; i < s1.size(); i++) {
  //   ll n1 = stoll(s1.substr(i, 1));
  //   ll n2 = stoll(s2.substr(i, 1));

  //   if (n1 > n2) {
  //     return 1;
  //   }
  //   if (n1 < n2) {
  //     return -1;
  //   }
  // }
  return 0;
}

int main() {
  for (ll i = 0; i < 10050; i++) {
    dp[i] = "";
  }

  map<ll, ll> m;
  m[1] = 2;
  m[2] = 5;
  m[3] = 5;
  m[4] = 4;
  m[5] = 5;
  m[6] = 6;
  m[7] = 3;
  m[8] = 7;
  m[9] = 6;

  ll N, M;
  scanf("%lld %lld", &N, &M);

  vector<ll> list(M);
  for (ll i = 0; i < M; i++) {
    ll v;
    scanf("%lld", &v);
    list[i] = v;
  }

  for (ll i = 0; i < N; i++) {
    for (ll j = 0; j < list.size(); j++) {
      if (dp[i].size() == 0 && i > 0) {
        continue;
      }

      ll n = list[j];
      ll required = m[n];

      // cout << "required:" << required << endl;

      string new_ch = to_string(n);

      // cout << "new_ch:" << new_ch << endl;
      string new_string = dp[i] + new_ch;

      // cout << "new_string:" << new_string << endl;

      if (compare(new_string, dp[i + required]) == 1) {
        dp[i + required] = new_string;
        // cout << i << "->" << i + required << ":" << new_string << endl;
      }
    }
  }

  // for (ll i = 0; i <= N; i++) {
  //   cout << i << ":" << dp[i] << endl;
  // }
  cout << dp[N] << endl;
}


Measured memory_bytes: 43776
import java.util.*;

public class Main {

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

//        long max = 42875000000L;
        long n = scanner.nextLong();

        long h;
        if (n > 2){
            for (int i = 1; i <= 3500; i++) {
                boolean found = false;
                for (int j = 1; j <= 3500; j++) {
                    if ((4*i*j - i*n - j*n) > 0){
                        h = i*j*n/(4*i*j - i*n - j*n);
                        if (h > 0 && h*(4*i*j - i*n - j*n) == i*j*n){
                            System.out.println(i + " " + j + " " + h);
                            found = true;
                            break;
                        }
                    }
                }
                if (found)break;
            }
        }
        else {
            if (n == 2) System.out.println("1 2 2");
        }
    }
}


Measured memory_bytes: 23764
# coding=utf-8

def count(list, target, num):
    l = len(list)
    c = 0
    for i in xrange(-num, l + 1):
        if list[-i] == target:
            c += 1
            if c == 4:
                return c
        else:
            return c
    return c


N = int(raw_input())
A = map(int, raw_input().split())

candidates = []
A.sort()
t = -1
for i in xrange(0, N + 1):
    n = count(A, A[t], t)
    for m in range(n / 2):
        candidates.append(A[t])
        if len(candidates) == 4:
            break
    t -= n
    if t < -N:
        break
if len(candidates) < 2:
    print 0
else:
    print candidates[0] * candidates[1]


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

using namespace std;

typedef long long int LL;
typedef unsigned long long int ULL;
typedef pair<int, int> PII;
typedef map<int, int> MII;

const int SZ = 112345;
const int MOD = 1e9 + 7;

int n, h, dp[1001][10001];
PII a[SZ];

int solve(int i, int H) {
  if (H <= 0) {
    return 0;
  }
  if (i == n && H > 0) {
    return MOD;
  }
  if (dp[i][H] == -1) {
    int r1 = solve(i, H - a[i].first) + a[i].second;
    int r2 = solve(i + 1, H);
    dp[i][H] = min(r1, r2);
  }
  return dp[i][H];
}

int main() {
  scanf("%d%d", &h, &n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &a[i].first, &a[i].second);
  }
  memset(dp, -1, sizeof dp);
  cout << solve(0, h) << endl;
  return 0;
}


Measured memory_bytes: 39808
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		String s = sc.next();
		
		// 計算
		int[] result = new int[s.length()];
		char c = 'R';
		int cnt = 1;
		for(int i = 0; i < s.length(); i++){
		    if(i == 0){
		        c = s.charAt(i);
		    }else if(c == s.charAt(i)){
		        cnt++;
		    }else{
		        result[i-1] += (cnt+1)/2;
		        result[i] += cnt/2;
		        cnt = 0;
		    }
		}
		cnt = 1;
		for(int i = s.length()-1; i >= 0; i--){
		    if(i == s.length()-1){
		        c = s.charAt(i);
		    }else if(c == s.charAt(i)){
		        cnt++;
		    }else{
		        result[i+1] += (cnt+1)/2;
		        result[i] += cnt/2;
		        cnt = 0;
		    }
		}
		
		// 出力
		for(int i = 0; i < s.length(); i++){
		    System.out.print(result[i] + " ");
		}
	}
}


Measured memory_bytes: 47816