akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define clr(x,i) memset(x,i,sizeof(x))
using namespace std;
const int N=1000005;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0',ch=getchar();}
    return x*f;
}
vector<int> d[N];
int n,a[N],cnt[N],vis[N],vis2[N];
void solve()
{
	n=read();
	for(int i=1; i<=n; i++) a[i]=read(),cnt[a[i]]++;
	int g=a[1];
	for(int i=2; i<=n; i++) {
		g=__gcd(g, a[i]);
	}
	if(g > 1) {puts("not coprime"); return;}
	vis[1] = 1;
	for(int i=2; i<=1000000; i++) if(!vis[i]) {
		d[i].push_back(i);
		for(int j=i+i; j<=1000000; j+=i) {
			vis[j] = 1;
			d[j].push_back(i);
		}
	}
	int fl=1;
	for(int i=1; i<=n; i++) {
		for(auto x:d[a[i]]) {
			if(vis2[x]) { fl=0; break; }
			vis2[x] = 1;
		}
		if(!fl) break;
	}
	if(fl) puts("pairwise coprime");
	else puts("setwise coprime");
}
int main()
{
	int T=1;
	while(T--) solve();
}

Measured memory_bytes: 71052
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/rope>

using namespace __gnu_pbds; 
using namespace __gnu_cxx;
using namespace std;
using ll = long long;

#define eb emplace_back
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define len(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define precision(n) fixed<<setprecision(n)

#ifdef LOCAL
    #include "debug.h"
#else
    #define debug(...) 42
#endif

void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);    
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
}

template<typename T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update >;
template<typename T> using MinPriorityQueue = priority_queue <T, vector <T>, greater <T> >;
template<typename T> void done(T ans) {cout << ans << "\n"; exit(0);}


template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}
 
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}

 

const int mod = 1e9;
const int N = 3e5 + 5;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937_64 mt(seed);

template <typename T>
long long myrand(T m) {
    long long md = m;
    long long x = mt()%md;

    return x;
}

vector<int> a(N);
vector <int> ans(N);
vector <int> adj[N];
vector<int> lis;

void dfs2(int node, int parent) {
    int idx = lower_bound(lis.begin(), lis.end(), a[node]) - lis.begin();
    int del = 1e9;
    
    if(idx == lis.size()) {
        del = -1;
        lis.push_back(a[node]);
    }
    else {
        del = lis[idx];
        lis[idx] = a[node];
    }

    ans[node] = lis.size();
    
    for(auto child : adj[node])
        if(child != parent) 
            dfs2(child,node);

    if(del == -1)
        lis.pop_back();
    else
        lis[idx] = del;
}

int main()
{
    io();
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) 
        cin >> a[i];
    for(int i = 0 ; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; 
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs2(0, -1);
    for(int i = 0; i < n; i++)
        cout << ans[i] << "\n";
}



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

int main() {
  int a, b;
  char o;
  cin >> a >> o >> b;
  int result = (o == '+') ? (a + b) : (a - b);
  cout << result << endl;
}



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

using namespace std;

int main() {
    
    //forItachi
	int a[3][3];
	int i,j,k;
	for(i=0;i<3;i++){
	    for(j=0;j<3;j++){
	        int x;
	        cin>>x;
	        a[i][j] = x;
	    }
	}
	int n;
	cin>>n;
	for(k=0;k<n;k++){
	    int y;
	    cin>>y;
	    for(i=0;i<3;i++){
	    for(j=0;j<3;j++){
	        
	        if(a[i][j]==y){
	            a[i][j] = 0;
	        }
	    }
	}
	}
	int status1 = 0,status2 = 0,status3=0;
	if((a[0][0]==0&&a[1][0]==0&&a[2][0]==0)||(a[0][1]==0&&a[1][1]==0&&a[2][1]==0)||(a[0][2]==0&&a[1][2]==0&&a[2][2]==0))
    cout<<"Yes"<<endl;
    else if((a[0][0]==0&&a[0][1]==0&&a[0][2]==0)||(a[1][0]==0&&a[1][1]==0&&a[1][2]==0)||(a[2][0]==0&&a[2][1]==0&&a[2][2]==0))
    cout<<"Yes"<<endl;
    else if((a[0][0]==0&&a[1][1]==0&&a[2][2]==0)||(a[0][2]==0&&a[1][1]==0&&a[2][0]==0))
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
    
}

Measured memory_bytes: 256
def resolve():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 998244353
    modinv = pow(2, mod - 2, mod)
    dp = [0] * (s + 1)
    dp[0] = pow(2, n, mod)
    for i in a:
        for j in range(s - i, -1, -1):
            dp[j + i] += dp[j] * modinv
            dp[j + i] %= mod
    print(dp[-1])


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9320
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>



template<class Container>
auto me(const Container& c) {
	return std::max_element(std::begin(c), std::end(c));
}


auto exec2() {
	int N{};

	int tab1[100005]{}, tab2[100005]{};
	std::cin >> N;

	for (int i{0}; i < N/2; i++) {
		int tmp{};
		std::cin >> tmp; tab1[tmp] += 1;
		std::cin >> tmp; tab2[tmp] += 1;
	}

	auto it1 = me(tab1);
	auto d1 = std::distance(std::cbegin(tab1), it1);
	
	auto it2 = me(tab2);
	auto d2 = std::distance(std::cbegin(tab2), it2);
	
	auto valid = 0;
	if (d1 == d2) {
		valid = std::max(*it1, *it2);
		tab1[d1] = tab2[d1] = 0;
		auto it12 = me(tab1);
		auto it22 = me(tab2);
		valid += std::max(*it12, *it22);
	}else {
		valid = (*it1) + (*it2);
	}
	std::cout << N- valid << "\n";

}

int main() {

	exec2();
	return 0;
}


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

# define ll long long

int main(){
  
  ll untastyAntidote, tastyAntidote, tastyPoison;
  cin >> untastyAntidote >> tastyAntidote >> tastyPoison;
  
  ll ans = tastyAntidote + min(untastyAntidote + tastyAntidote + 1, tastyPoison);
  cout << ans << endl;
  return 0;
} 

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int main()
{
    int n, t, a;
    cin >> n >> t >> a;
    vector<int> h(n);
    rep(i, n) cin >> h[i];

    int res = 1001001001;
    int ans;
    rep(i, n)
    {
        int ave_temp = 1000 * t - 6 * h[i];
        if (abs(ave_temp - 1000 * a) <= res)
        {
            res = abs(ave_temp - 1000 * a);
            ans = i;
        }
    }
    cout << ans + 1 << endl;

    return 0;
}


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

int main() {
  int A,B;
  cin >> A >> B;
  string a,b;
  for (int i = 0; i < B; i++) a += to_string(A);
  for (int i = 0; i < A; i++) b += to_string(B);
  if (a == b) {
    cout << a << endl;
  }else if (a < b) {
    cout << a << endl;
  }else {
    cout << b << endl;
  }
}

Measured memory_bytes: 256
//////////////////////////////
// Author: whatisit
// Date: 2020-05-13 04:03 
//////////////////////////////
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+2;

void solve() {
	int n, m, h[N], g[N] = {0}, a, b, ans = 0;
	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> h[i+1];
	for (int i = 0; i < m; ++i) {
		cin >> a >> b;
		g[a] = max(h[b], g[a]);
		g[b] = max(h[a], g[b]);
	}
	for (int i = 0; i < n; ++i) ans += h[i+1] > g[i+1];
	cout << ans;
}

int main() {
	//cin.tie(0); ios_base::sync_with_stdio(0);
	solve();
	return 0;
}

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

int main(){
	// sengen
	long n;
	// nyuryoku
	cin >> n;
	// keisan
	long sum = 1;
	long s = pow(10,9) + 7;
	for(int i=1;i<n+1;i++){
		sum = sum*i%s;
	}
	cout << sum;
}

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

int main(int argc, char const *argv[])
{
	int n,x;
	cin>>n>>x;
	int m,mi=1000000;;
	for (int i = 0; i < n; ++i)
	{
		cin>>m;
		x-=m;
		mi=min(mi,m);
	}
	cout<<n+x/mi<<endl;
	return 0;
}


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

#define forn(i,n) for(ll i = 0;i<n;i++)
#define forne(i,j,n) for(ll i = j;i<n;i++)
const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ll INF = 1000000001;
const ll N = 100001;
const lld PI = 3.141593;
#define F first
#define pb(a) push_back(a)
#define S second
#define pii pair<int,int>
typedef pair<ll,ll> pll;

lld powm(ll base,ll exp) {
	ll ans=1;
	while(exp){
		if(exp&1) ans=(ans*base)%mod;
		exp>>=1,base=(base*base)%mod;
	}
	return ans;
}

// ll dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// bool valid(ll i, ll j) {
// 	return i >= 1 && i <= n && j >= 1 && j <= m; 
// }
// int maxdepth = INT_MAX;
// vector<int> edgeVector[100000];
// ll minans = 1;
// printf("1 %d D\n",abs(r));
// priority_queue<ll,vector<ll>,greater<ll>> pq;
// ll a[N],b[N];
// vector<vector<ll>> adj(N);
// vector<set<ll>> adjs(N);
// ll adj[1001][1001];
// vector<vector<ll>> ans(1001);
// bool visited[N];
// ll cnt[1001];
// ll h,c,t;
// vector<pair<int, pair<int, int> > > g[300043];


int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output1.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

char c;
cin>>c;
if(isupper(c)){
	cout<<"A"<<endl;
}
else cout<<"a"<<endl;


}

Measured memory_bytes: 3648
import java.util.Scanner;
public class Main {
	
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        
        if( A-B > C ){
        	System.out.println( 0 );
        }
        else{
        	System.out.println( C - (A-B) );
        }
        
        sc.close();
    }
}

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

typedef long long ll;

int main(){
    int N, M, C;
    cin >> N >> M >> C;
    vector<int> B(M);
    for(int i = 0; i < M; i++){
        cin >> B.at(i);
    }

    int ans = 0;
    for(int i = 0; i < N; i++){
        int tmpsum = 0;
        for(int j = 0; j < M; j++){
            int tmp;
            cin >> tmp;
            tmpsum += tmp * B.at(j);
        }
        if(tmpsum + C > 0) ans++;
    }
    cout << ans << endl;


}


Measured memory_bytes: 256
let get_3_ints () = Scanf.scanf "%d %d %d" (fun u v w -> u,v,w)
let range ?(stride=1) u v =
  let rec f0 i a = if i>v then a else f0 (i+stride) (i::a)
  in f0 u []
let digits v =
  let rec f0 p a = if p=0 then a else f0 (p/10) ((p mod 10)::a)
  in f0 v []

let () =
  let (n,a,b) = get_3_ints ()
  in range 1 n
  |> List.fold_left (fun u v ->
    let k = v |> digits |> List.fold_left (+) 0
    in if a<=k&&k<=b then u+v else u
  ) 0
  |> Printf.printf "%d\n"

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a, b;
    cin >> a >> b;
    vector<char> s(a.size());
    vector<char> t(b.size());
    for(int i = 0; i < a.size(); i++)
    {
        s[i] = a[i];
    }
    for(int i = 0; i < b.size(); i++)
    {
        t[i] = b[i];
    }
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());
  
    for(int i = 0; i < min(s.size(), t.size()); i++)
    {
        if(s[i] == t[i])
        {
            continue;
        }
        else if(s[i] > t[i])
        {
            cout << "No" << endl;
            return 0;
        }
        else
        {
          cout << "Yes" << endl;
          return 0;
        }
    }
    if(s.size() < t.size())
    {
      cout << "Yes" << endl;
    }
    else
    {
      cout << "No" << endl;
    }
}



Measured memory_bytes: 256
A, B = list(map(int, input().split()))
S = input()
def judge(A, B, S):
    if S[A] != '-':
        return False
    S = S[:A] + S[A+1:]
    num = '0123456789'
    for x in S:
        if x not in num:
            return False
    return True

if judge(A, B, S):
    print("Yes")
else:
    print("No")



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

#define DEBUG

#ifdef DEBUG
#define dump(x) cout << "[*] " #x ": " << x << endl
#define debug(x) x
#else
#define dump(x)
#define debug(x)
#endif

//#define int long long
typedef long long ll;
//constexpr int INF = 1e9;
//constexpr int MOD = 1000000007;

decltype(1) main() {
    //cin.tie(nullptr);
    //ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    for (char& c : s) {
        cout << (c == '1' ? '9' : '1');
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		long x = sc.nextLong();
		long k = sc.nextLong();
		long d = sc.nextLong();
		
		if(x < 0) {
			x *= -1;
		}
		
		long div = x / d;
		
		if(div >= k) {
			System.out.println(x - k*d);
			return;
		}
		
		long remain = k - div;
		
		if(remain % 2 == 0) {
			System.out.println(x%d);
		}
		else {
			System.out.println(Math.abs(x%d - d));
		}
	}
}

Measured memory_bytes: 27096
import sys,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()
print(50)
a = [i + n//(50) for i in range(50)]

if n%(50) == 0:
    print(jo(a))
else:
    for i in range(50):
        if n%(50) >= i+1:
            a[i] += 50 - n%(50) +1
        else:
            a[i] -= n%(50)
    print(jo(a))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 51;
vector<int> adj[MAXN];
int d[MAXN], f[MAXN];
long long cur[MAXN], pre, x, y;

void dfs(int u, int dep, int p = 0){
	d[u] = dep;
	f[u] = p;
	for (int v : adj[u]){
		if (v != p){
			dfs(v, dep + 1, u);
		}
	}
}

void lca(int u, int v){
	if (d[u] < d[v]){
		swap(u, v);
	}
	while (d[u] > d[v]){
		x |= (1ll << u);
		u = f[u];
	}
	if (u == v){
		return;
	}
	while (u != v){
		x |= (1ll << u);
		y |= (1ll << v);
		u = f[u];
		v = f[v];
	}
}

int main(){
	ios::sync_with_stdio(0);
	cout << setprecision(10) << fixed;
	long long  n;
	cin >> n;
	for (int i = 0; i < n - 1; ++i){
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0);
	int m;
	cin >> m;
	long long ans = 0;
	for (int i = 0; i < m; ++i){
		int u, v;
		cin >> u >> v;
		x = 0;
		y = 0;
		lca(u, v);
		cur[i] = x ^ y;
	}
	int mx = (1 << m);
	for (int i = 0; i < mx; ++i){
		long long num = 0ll;
		int cnt = 0;
		for (int j = 0; j < m; ++j){
			if (i & (1 << j)){
				cnt++;
				num |= cur[j];
			}
		}
		ans += (1ll << (n - 1 - __builtin_popcountll(num))) * (cnt % 2 ? -1ll : 1ll);
	}
	cout << ans;
	return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner scan = new Scanner(System.in);

		String w = scan.next();
		while (w.length() % 2 == 0 && w.length() != 0) {
			w = w.replace(String.valueOf(w.charAt(0)), "");
		}
		if (w.length() == 0) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 21716
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 100010;
int a[Maxn], n;
bool cmp(int x, int y) { return x > y; }
int main() {
	int i, j, k;
	scanf("%d", &n);
	for(i = 0; i < n; i++) scanf("%d", &a[i]);
	sort(a, a+n, cmp);
	for(i = 0; i <= n; i++){
		if(i+1 >= a[i+1]){
			int u = (a[i]-i+1)&1;
			int v = 1;
			while(i < a[i+v-1]) v++;
			u |= v&1;
			if(u == 1) printf("First\n");
			else printf("Second\n");
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;

ll a[100000];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    ll mi = 1e9, sum = 0, cnt = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        cnt ^= a[i] < 0;
        sum += abs(a[i]);
        mi = min(mi, abs(a[i]));
    }

    if (cnt)
        cout << sum - 2 * mi;
    else
        cout << sum;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000 + 20 ;
long long inf = 1e18;
long long a[MAXN], ev[MAXN], root[MAXN];
bool vis[MAXN];
vector <int> vec[MAXN];

void dfs(int u, int v) {
	vis[u] = 1;
	root[u] = 1;
	for (int i = 0; i < vec[u].size(); i++)
		if (!vis[vec[u][i]]) {
			dfs(vec[u][i], u);
			if(ev[vec[u][i]] == 0) {
//				cout << "X1 ";
				cout << u << " " << vec[u][i] << endl;
				ev[u] = abs(ev[u] - 1);
			}
			else {
//				cout << "X2 ";
				cout << vec[u][i] << " " << u << endl;
				ev[vec[u][i]] = abs(ev[vec[u][i]] - 1);
			}
		}
		else
			if(root[vec[u][i]] == 0) {
//				cout << "X3 ";
				cout << u << " " << vec[u][i] << endl;
				ev[u] = abs(ev[u] - 1);
			}
			
	root[u] = 0;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	
	int u, v;
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	
	if (m % 2 == 1)
		return cout << -1, 0;
		
	for(int i = 1; i <= n; i++)
		if(vec[i].size() > 1) {
			dfs(i, 0);
			return 0;
		}
}	

	
 
	

	
	
	

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

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

    ll a, b, c, k;
    cin >> a >> b >> c >> k;

    ll ans = 0;
    if(k >= a) {
        ans += a;
        k -= a;
    }
    else {
        ans = k;
        cout << ans << '\n';
        return 0;
    }

    if(k >= b) {
        k -= b;
    }
    else {
        cout << ans << '\n';
        return 0;
    }

    ans -= k;
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
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; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define pri_que priority_queue
#define vint vector<int>
#define vvint vector<vector<int>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vs vector<string>
#define vvc vector<vector<char>>
#define vc vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e15;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n; cin >> n;
    vi a(n);
    rep(i,n){
        cin >> a[i];
        a[i]--;
    }
    int res=0;
    rep(i,n){
        if(a[a[i]]==i) res++;
    }
    cout<<res/2<<endl;
}

Measured memory_bytes: 3980
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    LL n;
    cin >> n;
    VI a(n);
    REP(i,0,n) cin >> a[i];
    multiset<int> s;
    s.insert(a[0]);
    //int cnt = 1;
    REP(i,1,n) {
        auto it = s.lower_bound(a[i]);

        if (it == s.begin()) {
            s.insert(a[i]);
            //++cnt;
        } else {
            --it;
            s.erase(it);
            s.insert(a[i]);
        }
    }
    //cout << cnt << endl;
    std::cout << s.size() << endl;
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 5376
import java.util.Scanner;
import java.util.SortedSet;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			sc.nextInt();
			SortedSet<Integer> set = new TreeSet<>();
			while (sc.hasNext()) {
				set.add(sc.nextInt());
			}
			int min = set.first();
			if (min == 1 || set.size() == 1) {
				System.out.println(min);
			} else {
				while (set.size() != 1) {
					int max = set.last();
					set.remove(max);
					if (max % set.last() == 0) {
						continue;
					} else {
						set.add(max % set.last());
					}
				}
				System.out.println(set.last());
			}
		}
	}
}

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

using namespace std;

#define ll long long;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

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

    string s;
    cin >> s;
    REP(i, s.size()) {
        if(i%2 == 0) cout << s[i];
    }
    cout << endl;

}



Measured memory_bytes: 592
#include<iostream>
#include<string>
using namespace std;
int main(){
  string str;
  int ab[26]={};
  int i;
  while(getline(cin,str)){
    for(i=0;i<str.size();i++){
      if(str[i]>='a'&&str[i]<='z') ab[str[i]-'a']++;
      else if(str[i]>='A'&&str[i]<='Z') ab[str[i]-'A']++;
    }
  //cout << str << endl;
  }
  for(i=0;i<26;i++){
    cout << (char)('a'+i) << " : " << ab[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 3196
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;


void merge(int A[], int n, int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;
  for(int i = 0; i < n1; i++) L[i] = A[left + i];
  for(int i = 0; i < n2; i++) R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  int i= 0, j = 0;
  for(int k = left; k < right; k++){
    cnt++;
    if(L[i] <= R[j]){
      A[k] = L[i++];
    }else{
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[], int n, int left, int right){
  if(left+1 < right){
  int mid = (left + right)/2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid,right);
    merge(A,n,left,mid,right);
  }
}



int main(){
  int  A[MAX], n, i;
  cnt = 0;

  cin >> n;
  for(i = 0; i < n; i++) cin >> A[i];

  mergeSort(A, n, 0, n);

  for(i = 0; i < n; i++){
    if( i ) cout << " ";
    cout << A[i];
  }
  cout << endl;
  cout << cnt << endl;
  
  return 0;
}
			 



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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);

int n,a,f;
set<int> s;

main() {
    cin >> n;
    rep(i,n) {
        cin >> a;
        int hoge=400;
        if (a>=3200) f++;
        else rep1(i,8) if (a<hoge*i) {s.insert(i);break;}

    }
    if (f) {cts(max((int)1,(int)s.size()))ct(s.size()+f)}
    else {cts(s.size())ct(s.size())}

}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define str to_string
#define endl "\n"
#define PI 3.141592653589
using namespace std;
using lint = long long;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

//AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC
int main(){
    int ans=0,n;cin>>n;
    vector<int> vec(n);for(int i=0;i<n;i++){cin>>vec[i];vec[i]--;}
    for(int i=0;i<n;i++){
        if(vec[vec[i]]==i)ans++;
    }
    cout<<ans/2<<endl;
}


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

#define MAXN1 50000
#define MAXN2 50000
#define MAXM 150000

using namespace std;

int n1, n2, edges, last[MAXN1];
int preve[MAXM];
int head[MAXM];
int matching[MAXN2], dist[MAXN1], Q[MAXN1];
bool used[MAXN1], vis[MAXN1];

void init(int _n1, int _n2) {
  n1=_n1;
  n2=_n2;
  edges=0;
  fill(last, last + n1, -1);
}

void add_edge(int u, int v) {
  head[edges]=v;
  preve[edges] = last[u];
  last[u] = edges++;
}

void bfs() {
  fill(dist,dist+n1,-1);
  int sizeQ=0;
  for (int u=0;u<n1;u++) {
    if (!used[u]) {
      Q[sizeQ++]=u;
      dist[u]=0;
    }
  }
  for (int i=0;i<sizeQ;i++) {
    int u1 = Q[i];
    for (int e=last[u1];e>=0;e=preve[e]) {
      int u2 = matching[head[e]];
      if (u2>=0 && dist[u2]<0) {
	dist[u2]=dist[u1]+1;
	Q[sizeQ++]=u2;
      }
    }
  }
}

bool dfs(int u1) {
  vis[u1]=true;
  for (int e=last[u1];e>=0;e=preve[e]) {
    int v=head[e];
    int u2=matching[v];
    if (u2<0 || (!vis[u2] && dist[u2]==dist[u1]+1 && dfs(u2))) {
      matching[v]=u1;
      return used[u1]=true;
    }
  }
  return false;
}

int bipartite_matching() {
  fill(used,used+n1,false);
  fill(matching,matching+n2,-1);
  for (int res=0;;) {
    bfs();
    fill(vis,vis+n1,false);
    int f=0;
    for(int u=0;u<n1;u++)
      if(!used[u] && dfs(u))f++;
    if (!f)return res;
    res+=f;
  }
}

int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}

int main(void){
  
  int m,n;
  
  while(cin >> m >> n,m|n){
 
    init(m,n);
    
    vector<int>b(m),r(n);
    for(int i=0;i<m;i++)cin >> b[i];
    for(int i=0;i<n;i++)cin >> r[i];
    
    for(int i=0;i<m;i++){
      for(int j=0;j<n;j++){
	if(gcd(b[i],r[j])!=1)add_edge(i,j);
      }
    }

    cout << bipartite_matching() << endl;
  }
  
  return 0;
}

Measured memory_bytes: 2148
S = str(input())

if S == "SUN":
  print(7)
elif S == "MON":
  print(6)
elif S == "TUE":
  print(5)
elif S == "WED":
  print(4)
elif S == "THU":
  print(3)
elif S == "FRI":
  print(2)
else:
  print(1)

Measured memory_bytes: 3060
import sys
input = sys.stdin.readline

def main():
    n,k = map(int, input().split())
    ans = 0
    for b in range(k+1, n+1):
        c = 0
        a = k+c*b
        while a <= n:
            if a != 0:
                if a+b-k <= n:
                    ans += b-k
                else:
                    ans += n-a+1
            else:
                if a+b-k <= n:
                    ans += b-k-1
                else:
                    ans += n-a
            c += 1
            a = k+c*b
    print(ans)

if __name__ == "__main__":
    main()

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

int main(){
    int H,A;
    cin >> H >> A;
    int ans = H/A;
    if(H%A != 0) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,ma=0;
    string a="";
    cin>>n;
    map<string ,int>m;
    for(int i=0;i<n;i++)
    {
    string s;
    cin>>s;
    m[s]++;
        if(ma<m[s])
        {
            ma=m[s];
            //a=s;
        }
    }
   map<string, int>::iterator itr;
    for(itr=m.begin();itr!=m.end();itr++)
    {
        if(itr->second==ma)
        cout<<itr->first<<"\n";

    }
    //cout<<a;
}


Measured memory_bytes: 25216
import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

def D(a,b,c):
    return abs(a-b) + abs(b-c)

def getAns(x):
    ret = 10**18
    U = [S, T]
    for k in range(len(U)):
        u = U[k]
        v = U[(k-1)%2]
        idx = bisect.bisect_left(u, x)
        for i in [idx-1, idx]:
            if not 0<=i<len(u):
                continue
            idxx = bisect.bisect_left(v, u[i])
            for j in [idxx-1, idxx]:
                if 0<=j<len(v):
                    ret = min(ret, D(x, u[i], v[j]))
    return ret

for x in X:
    print(getAns(x))





Measured memory_bytes: 97472
W,H,N = map(int,input().split())
W0 = 0
H0 = 0
for i in range(N):
    x,y,a = map(int,input().split())
    if a == 1:
        if x >= W:
            W0 = W
        elif x >= W0:
            W0 = x
    elif a == 2:
        if x <= W0:
            W = W0
        elif x <= W:
            W = x
    elif a == 3:
        if y >= H:
            H0 = H
        elif y >= H0:
            H0 = y
    else:
        if y <= H0:
            H = H0
        elif y <= H:
            H = y
print((W-W0)*(H-H0))

Measured memory_bytes: 3064
<?php
//error_reporting(0);
//$N = trim(fgets(STDIN));
list($N,$H,$W) = explode(" ",trim(fgets(STDIN)));
//$a = explode(" ",trim(fgets(STDIN)));
//$H = explode(" ",trim(fgets(STDIN)));
$res=0;
for($i=0;$i<$N;$i++) {
  list($A,$B) = explode(" ",trim(fgets(STDIN)));
  if ($A >= $H && $B >= $W) {
    $res++;
  }
}
printf("%d\n",$res);


Measured memory_bytes: 3828
// 2011/05/31 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int n;
		cin >> n;
		if(cin.eof())
			break;

		int cnt = 0;
		for(int a=0; a<=9; a++){
			if(a>n)
				break;
			for(int b=0; b<=9; b++){
				if(a+b>n)
					break;
				for(int c=0; c<=9; c++){
					if(a+b+c>n)
						break;
					for(int d=0; d<=9; d++){
						if(a+b+c+d>n)
							break;
						if(a+b+c+d==n)
							cnt++;
					}
				}
			}
		}

		cout << cnt << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main()
{
  int X, Y;
  cin >> X >> Y;

  bool found = false;

  rep(i, X + 1)
  {
    if (i * 2 + (X - i) * 4 == Y)
    {
      found = true;
      break;
    }
  }

  if (found)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 3616
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
INF = 500000
mod = 10**9+7

l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())-1
print(l[K])

# a, b, c = input(), input(), input()
# la, lb, lc = len(a), len(b), len(c)
# for i in range(1, min(la, lb)):
#     S = ''
#     for j in range(i):
#         if a[la-i+j] == b[j]:
#             S += b[j]
#             continue
#         elif a[la-i+j] == '?':
#             S += b[j]
#         elif b[j] == '?':
#             S += c[j]


Measured memory_bytes: 3316
N = int(input())                    
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
                                    
result = []                         
                                    
for n in range(N):                  
    a1 = sum(A1[:n+1])              
    a2 = sum(A2[n:])                
    result.append(a1+a2)            
                                    
print(max(result))                  

Measured memory_bytes: 38512
//srinivas
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
using namespace __gnu_pbds;
using namespace std;

#define all(c) (c).begin(),(c).end()
#define endl "\n"
#define ff first
#define ss second
#define allr(c) (c).rbegin(),(c).rend()
#define fr(x,in,n,r) for(ll x=in;x<n;x+=r)
#define ifr(x,n) for(ll x=0;x<n;x++)
#define dfr(x,n) for(ll x=n-1;x>=0;x--)
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define pof(a) pop_front(a)
#define pob(a) pop_back(a)
#define eb(a) emplace_back(a)
#define ef(a) emplace_front(a)
#define fstm(m,n,r) m.reserve(n);m.max_load_factor(r)
#define os tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
typedef map<ll,ll> mll;
typedef map<string,ll> msll;
typedef unordered_map<ll,ll> umap;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mod 1000000007
#define N 100001

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

    ll n;
    cin>>n;
    ld a[n];
    ifr(i,n)cin>>a[i];
    ld dp[n][(n+1)/2];
    ifr(i,n)ifr(j,(n+1)/2)dp[i][j]=0;
    dp[0][0]=a[0];
    fr(i,1,n,1)
        dp[i][0]=dp[i-1][0]*a[i];
    dp[0][1]=1-a[0];
    fr(i,1,n,1){
        fr(j,1,min(i+2,(n+1)/2),1)
            dp[i][j]=(dp[i-1][j-1]*(1-a[i]))+(dp[i-1][j]*a[i]);
    }
    ld ans=0;
    ifr(i,(n+1)/2)
        ans+=dp[n-1][i];
    cout<<setprecision(10)<<fixed;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
int main()
{
      int n,m;
       cin>>n>>m;

        int arr[m];

       long int sum=0;

        for(int i=0;i<m;i++)
        {
            cin>>arr[i];
            sum+=arr[i];
        }
         if(sum > n)
          cout<<"-1";

          else
         cout<<n-sum;
}


Measured memory_bytes: 3628
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
 
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

#define MOD 1000000007LL
#define HMAX 500

int N;
vector<int> P;
int mhate[500][500];
bool sheet[500][500];
ll ans;

void update(int x, int y) {
  int nh;

  if (x<0 || x>=N || y<0 || y>=N) return;
  nh = mhate[x][y];
//printf("update(%d,%d)\n", x, y);

  if (x>0) {
    if (mhate[x-1][y] + sheet[x-1][y] < mhate[x][y]) {
      nh = min(mhate[x-1][y] + sheet[x-1][y], nh);
    }
  }
  if (x<N-1) {
    if (mhate[x+1][y] + sheet[x+1][y] < mhate[x][y]) {
      nh = min(mhate[x+1][y] + sheet[x+1][y], nh);
    }
  }
  if (y>0) {
    if (mhate[x][y-1] + sheet[x][y-1] < mhate[x][y]) {
      nh = min(mhate[x][y-1] + sheet[x][y-1], nh);
    }
  }
  if (y<N-1) {
    if (mhate[x][y+1] + sheet[x][y+1] < mhate[x][y]) {
      nh = min(mhate[x][y+1] + sheet[x][y+1], nh);
    }
  }
  if (nh < mhate[x][y]) {
//printf(" mhate[%d][%d] = %d -> %d\n", x, y, mhate[x][y], nh);
    mhate[x][y] = nh;
    update(x-1, y);update(x+1, y);update(x, y-1);update(x, y+1);
  }
}

void out(int o) {
  int x,y;

  //席o(座標(x,y))の人がいなくなった場合の座席のコスト変化

  x = (o-1)/N; y= (o-1)%N;

  ans += mhate[x][y];    //その席のコストが結果に加算される
//printf("out(%d) %d %lld\n", o, mhate[x][y], ans);
  sheet[x][y] = false;  //その席を空席にする

  //退席した人の前の人
  update(x-1, y);
  //退席した人の左の人
  update(x, y-1);
  //退席した人の後ろの人
  update(x+1, y);
  //退席した人の右の人
  update(x, y+1);
  update(x, y);
}

int main()
{

  cin >> N;
  P.resize(N*N);
  for (int i=0; i<N*N; i++) {
    cin >> P[i];
    mhate[i/N][i%N]=min(min(i/N,N-i/N-1),min(i%N, N-i%N-1));
    sheet[i/N][i%N] = 1;
  }

  for (int i=0; i<N*N; i++) {
    out(P[i]);
  }


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


Measured memory_bytes: 35584
#!/usr/bin/env python3

import sys

def solve(n, m, ls_py):
    # Uncomment the following if you want to check the input.
    # print('n =', n)
    # print('m =', m)
    # print('ls_py =', ls_py)
    perP = [[] for i in range(n+1)]
    for (i,[p,y]) in enumerate(ls_py):
        perP[p].append((y,i))
    seqs = []
    for p in range(n+1):
        perP[p].sort()
        for (o, (_, i)) in enumerate(perP[p], start=1):
            seq = '{:06d}{:06d}'.format(p, o)
            seqs.append((i,seq))
    return '\n'.join([seq for (i,seq) in sorted(seqs)])


def readQuestion():
    ws = sys.stdin.readline().strip().split()
    n = int(ws[0])
    m = int(ws[1])
    ls_py = [list(map(int, sys.stdin.readline().strip().split())) for j in range(m)]
    return (n, m, ls_py)

def main():
    print(solve(*readQuestion()))

# Uncomment before submission
main()


Measured memory_bytes: 60988
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    int x, y;
    string nap;
    cin >> x >> y >> nap;
    if (nap[x] != '-')
    {
        cout << "No";
        return 0;
    }
    nap.erase(x, 1);
    for (int i = 0; i < nap.size(); ++i)
    {
        if (!(nap[i] >= '0' && nap[i] <= '9'))
        {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int N;
int dp[110][5][5][5];

int rec(int n, int a, int b, int c) {
  if (n == N) return 1;
  if (dp[n][a][b][c] > 0) return dp[n][a][b][c];

  int res = 0;
  if (a == 0 && b == 2) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (b == 2 && c == 0) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (b == 0 && c == 2) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (b == 0 && c == 1) {
    for (int i = 0; i < 4; i++) {
      if (i != 2) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else if (a == 0 && c == 2) {
    for (int i = 0; i < 4; i++) {
      if (i != 1) {
        res += rec(n + 1, b, c, i);
        res %= MOD;
      }
    }
  } else {
    for (int i = 0; i < 4; i++) {
      res += rec(n + 1, b, c, i);
      res %= MOD;
    }
  }

  return dp[n][a][b][c] = res;
}

signed main() {
  cin >> N;
  cout << rec(0, 3, 3, 3) << endl;
  return 0;
}


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

using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); ++i)
double const PI = 3.1415926535897932384626433;
using P = pair<int, int>;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max(a * b, c * d) << endl;
    return 0;
}

Measured memory_bytes: 3612
/*
 * a.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  for (;;) {
    int m, f, r;
    cin >> m >> f >> r;
    if (m < 0 && f < 0 && r < 0) break;

    char ans;
    if (m < 0 || f < 0) ans = 'F';
    else {
      int sum = m + f;
      if (sum >= 80) ans = 'A';
      else if (sum >= 65) ans = 'B';
      else if (sum >= 50) ans = 'C';
      else if (sum >= 30) {
	if (r >= 50) ans = 'C';
	else ans = 'D';
      }
      else ans = 'F';
    }

    printf("%c\n", ans);
  }
  
  return 0;
}

Measured memory_bytes: 1144
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

fn solve() {
    input! {
        n: usize
    };

    let rest = n % 1000;
    let res = if rest == 0 { 0 } else { 1000 - rest };
    println!("{}", res);
}

fn main() {
    std::thread::Builder::new()
        .name("big stack size".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(|| {
            solve();
        })
        .unwrap()
        .join()
        .unwrap();
}


Measured memory_bytes: 2264
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
struct YPO
{
    ll w,r;
};
char c[200050];
ll a[200050];
YPO b[200050];
int main()
{
    ll n,i,j;
    scanf("%lld%s",&n,c);
    ll u=0;
    ll ci=0;  //全白或全红
    for(i=0;i<n;i++)
    {
        b[i].w=0; b[i].r=0;
        if(c[i]=='W')
        {
            ci++;
            a[i]=0;
        }
        else
        {
            u++;
            a[i]=1;
        }
    }
    ci=min(ci,u);
    if(a[0]==0)
        b[0].w++;
    else
        b[0].r++;
    for(i=1;i<n;i++)
    {
        if(a[i]==0)
        {
            b[i].w=b[i-1].w+1;
            b[i].r=b[i-1].r;
        }
        else
        {
            b[i].w=b[i-1].w;
            b[i].r=b[i-1].r+1;
        }
    }
    ll cs,ct,a1,a2,a3;
    for(i=0;i<n-1;i++)  //1个红到n-1个红
    {
        a1=b[i].w;
        a2=b[n-1].r-b[i].r;
        a3=abs(a1-a2);
        ct=min(a1,a2);
        cs=a3+ct;
        if(cs<ci)
            ci=cs;
    }
    printf("%lld\n",ci);
    return 0;
}


Measured memory_bytes: 8704
use proconio::{fastout, input};
use std::collections::VecDeque;

#[derive(Debug, Clone, Default)]
struct Cell {
    wait: usize,
    cost: usize,
    neighbors: Vec<usize>,
}

#[fastout]
fn main() {
    input! {in_n: usize};
    input! {in_ps: [usize; in_n * in_n]};

    let width = in_n + 2;
    let height = in_n + 2;
    let mut cells = Vec::new();

    for i in 0..(width * height) {
        let x = i % width;
        let y = i / width;
        let mut cell = Cell::default();

        if 0 < x && x < width - 1 && 0 < y && y < height - 1 {
            cell.wait = 1;
            cell.cost = *[x, width - x - 1, y, height - y - 1].iter().min().unwrap();
            cell.neighbors.push(i + 1);
            cell.neighbors.push(i - 1);
            cell.neighbors.push(i + width);
            cell.neighbors.push(i - width);
        }

        cells.push(cell);
    }

    let mut cost = 0;

    for in_p in in_ps {
        let x = (in_p - 1) % in_n + 1;
        let y = (in_p - 1) / in_n + 1;
        let i = x + y * width;

        cells[i].cost -= 1;
        cells[i].wait = 0;
        cost += cells[i].cost;

        let mut queue = VecDeque::new();

        queue.push_front(i);

        while !queue.is_empty() {
            let i = queue.pop_back().unwrap();

            for n in cells[i].neighbors.clone().iter() {
                let c = cells[i].cost + cells[*n].wait;

                if cells[*n].cost > c {
                    cells[*n].cost = c;
                    queue.push_front(*n);
                }
            }
        }
    }

    println!("{}", cost);
}


Measured memory_bytes: 27252
N = int(input())
A = [int(i) for i in input().split()]
dic = {}
ckd = []
ans = 0

for i in range(N):
  try:
    dic[A[i]] += 1
  except KeyError:
    dic[A[i]] = 1
    
tpl = dic.items()
for i in tpl:
  if i[0] > i[1]:
    ans += i[1]
  else:
    ans += i[1] - i[0]
    
print(ans)

Measured memory_bytes: 67240
#include <bits/stdc++.h>
using namespace std;
 
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair
 
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());


int gcd(int a, int b) { return a ? gcd(b%a,a) : b; }

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

    int g; cin >> g;
    cout << (360 / gcd(360,g)) << endl;

    return 0;
}


Measured memory_bytes: 3540
#include <cstdio>
#include <cstring>

int main() {
    const int coin[] = { 500, 100, 50, 10, 5, 1};
    int n = 0;

    while (scanf("%d", &n)) {
        if (n == 0) return 0;
        int c = 0;
        int o = 1000 - n;
        while (o != 0) {
            for (int i = 0; i < 6; ++i) {
                if (coin[i] <= o) {
                    o -= coin[i];
                    c++;
                    break;
                }
            }
        }
        printf("%d\n", c);
    }

    return 0;
}

Measured memory_bytes: 1028
use std::io::*;
use std::str::FromStr;
use std::cmp::{max};
use std::cell::RefCell;
use std::f64::consts::PI;

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

fn main() {
    let a: f64 = read();
    let b: f64 = read();
    let x: f64 = read();

    let h: f64 = x / a / a;
    let rest_h = b - h;
    if rest_h <= b / 2.0 {
        println!("{:.6}", (rest_h * 2.0 / a).atan() / PI * 180.0);
        return;
    }
    println!("{:.6}", (PI / 2.0 - (2.0 * x / (a * b * b)).atan()) / PI * 180.0);
}


Measured memory_bytes: 4476
q,h,s,d = map(int,input().split())
n = int(input())

l20 = [q*8,h*4,s*2,d]
l10 = [q*4,h*2,s]
l05 = [q*2,h]
l025 = [q]

cst = 0


if(n>=2):
    divi = int(n/2)
    cst += min(l20)*divi
    r = n%2
    n = r
if(n>=1):
    divi = int(n/1)
    cst += min(l10)*divi
    r = n%1
    n = r
if(n>=0.5):
    divi = int(n/0.5)
    cst += min(l05)*divi
    r = n%0.5
    n = r
if(n>=0.25):
    divi = int(n/0.25)
    cst += min(l025)*divi
    
print(cst)

Measured memory_bytes: 38384