akhauriyash/Code-Regression huggingface dataset:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N = NI()
    A = NLI()
    
    cumsum = [0 for _ in range(len(A)+1)] 
    cnt = A[0]
    cumsum[0] = A[0]
    for n in range(1,len(A)):#
        cumsum[n] = cumsum[n-1] + A[n]
        
    cumsum_c = collections.Counter(cumsum)
    
    cumsum_v = list(cumsum_c.values())
    
    # 組み合わせの総数
    def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
    ans = 0
    
    for i in cumsum_v:
        if not i == 1:
            ans += combinations_count(i, 2)
    print(ans)
    


if __name__ == '__main__':
    main()

Measured memory_bytes: 44216
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<(n);i++)
#define MOD 1000000007
#define all(n) (n).begin(),(n).end()
typedef long long ll;
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}else{return 0;}}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}else{return 0;}}
template <class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <class T> inline T LCM(T a,T b){return a*b/GCD(a,b);}



int main(){
	int n,a,b,c;
	string s;
	string x[]={"SUN","MON","TUE","WED","THU","FRI","SAT"};

	cin >> s;
	
	FOR(i,7){
		if(x[i]==s){
			cout << 7-i << endl;
			return 0;
		}
	}

}

Measured memory_bytes: 256
N=int(input())
for h in range(1,3501):
    if 4*h<=N:
        continue
    for w in range(h,3501):
        if 4*h*w>(h+w)*N and (N*h*w)%(4*h*w-(h+w)*N)==0:
            print(h,w,(N*h*w)//(4*h*w-(h+w)*N))
            exit()

Measured memory_bytes: 3060
#include <iostream>
#include <vector>

using namespace std;

vector<int> factorize(int n) {
	vector<int> ps;

	for (int i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			ps.push_back(i);
			n /= i;
		}
	}
	if (n != 1) ps.push_back(n);
	
	return ps;
}

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

	vector<int> ps = factorize(n);
	cout << n << ':';
	for (vector<int>::iterator it = ps.begin(); it != ps.end(); ++it) {
		cout << ' ' << *it;
	}
	cout << endl;

	return 0;
}

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

N = int(input())
S = input().rstrip()
mod = 10**9 + 7
cnt = 0
ans = 1
for c in S:
    if (c == 'W') ^ (cnt % 2 == 1):
        ans = ans * cnt % mod
        cnt -= 1
    else:
        cnt += 1
if cnt > 0:
    ans = 0
for i in range(1, N+1):
    ans = ans * i % mod
print(ans)

Measured memory_bytes: 41692
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,i;
	scanf("%d%d%d",&a,&b,&c);
	for(i=min(a,b);i>=1;i--)
	{
		if(a%i==0&&b%i==0)
			c--;
		if(c==0)
		{
			printf("%d",i);
			return 0;
		}
	}
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;

#define _ sync_with_stdio(false)
typedef long long ll;
const int MAXN=100000+10;
const int INF=0x7fffffff;

int a[7]={1,3,5,7,8,10,12};
int b[4]={4,6,9,11};
int c=2;
int main() {
	int x,y;
	scanf("%d%d",&x,&y);
	int ok=0;
	int f=0;
	for(int i=0;i<7;i++){
		if(a[i]==x)
			f++;
		if(a[i]==y)
			f++;
	}
	if(f==2)
		ok=1;
	f=0;
	for(int i=0;i<4;i++){
		if(b[i]==x)
			f++;
		if(b[i]==y)
			f++;
	}
	if(f==2)
		ok=1;
	if(c==x&&c==y)
		ok=1;
	if(ok)
		puts("Yes");
	else {
		puts("No");
	}
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
int n,a[200010],nw,ans=1e9;
int nxt[200010],pos[200010];
int num[200010],tot;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]),pos[a[i]]=i;
		if (pos[a[i]-1]) nxt[pos[a[i]-1]]=i;
		else num[++tot]=i;
	}
//	for (int i=1;i<=n;i++) printf("%d %d\n",nxt[i],pos[i]);printf("\n");
	for (int i=1;i<=tot;i++)
	{
		int nw=num[i],nans=0;
		while (nw) nans++,nw=nxt[nw];
		ans=min(ans,n-nans);
	}
	printf("%d",ans);
/*	nxt[0]=1;
	for (int i=1;i<=n;i++) nxt[i]=i+1,t[i]=i-1;
	nw=1;
	while (nw)
	{
		nw=0;int pre=a[nxt[0]]-1;
		for (int i=nxt[0];i<=n;i=nxt[i])
		{
			if (a[i]==pre+1)
			{
				pre++;nw++;
				nxt[t[i]]=nxt[i];
				t[nxt[i]]=t[i];
			}
		}
		ans=min(ans,n-nw);
	//	for (int i=1;i<=n;i++)
	//		printf("%d %d\n",t[i],nxt[i]);
	}
	printf("%d",ans);*/
}
 

Measured memory_bytes: 2944
use std::io::{stdout, Write, BufWriter};

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: usize,
        m: usize,
        c: i32,
        b: [i32; m],
        codes: [[i32; m]; n],
    }

    let mut ans = 0;
    for code in codes {
        let sum: i32 = code.iter().zip(b.iter()).map(|(a, b)| a * b).sum();
        if sum + c > 0 { ans+= 1; }
    }
    println!("{:?}", ans);
}


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

using namespace std;

struct queue
{
	vector<int> x;
	vector<int> y;
};

int main()
{
	int h, w;
	cin >> h >> w;
	
	char mp[h][w];
	int ans = 0;
	for(int i = 0; i < h; i++)
	{
		for(int j = 0; j < w; j++)
		{
			cin >> mp[i][j];
			if(mp[i][j] == '.')
			{
				ans++;
			}
		}
	}
	
	queue q;
	q.x.push_back(0);
	q.y.push_back(0);
	
	int map[h][w];
	for(int i = 0; i < h; i++)
	{
		for(int j = 0; j < w; j++)
		{
			map[i][j] = 99999;
		}
	}
	
	int distance = 0;
	int cnt = 0;
	int i = 0;
	while(q.x.empty() == false)
	{
		int tmp_x = q.x[0];
		int tmp_y = q.y[0];
		q.x.erase(q.x.begin());
		q.y.erase(q.y.begin());
		
		if(map[tmp_y][tmp_x] > distance)
		{
			map[tmp_y][tmp_x] = distance;
		}
		
		if(mp[tmp_y + 1][tmp_x] == '.' && tmp_y + 1 != h)
		{
			q.x.push_back(tmp_x);
			q.y.push_back(tmp_y + 1);
			i++;
			mp[tmp_y + 1][tmp_x] = '!';
		}
		
		if(mp[tmp_y - 1][tmp_x] == '.' && tmp_y - 1 != -1)
		{
			q.x.push_back(tmp_x);
			q.y.push_back(tmp_y - 1);
			i++;
			mp[tmp_y - 1][tmp_x] = '!';
		}
		
		if(mp[tmp_y][tmp_x + 1] == '.' && tmp_x + 1 != w)
		{
			q.x.push_back(tmp_x + 1);
			q.y.push_back(tmp_y);
			i++;
			mp[tmp_y][tmp_x + 1] = '!';
		}
		
		if(mp[tmp_y][tmp_x - 1] == '.' && tmp_x - 1 != -1)
		{
			q.x.push_back(tmp_x - 1);
			q.y.push_back(tmp_y);
			i++;
			mp[tmp_y][tmp_x - 1] = '!';
		}
		
		if(cnt > 1)
		{
			cnt--;
		}
		else
		{
			cnt = i;
			i = 0;
			distance++;
		}
	}
	
	if(map[h - 1][w - 1] == 99999)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << ans - map[h - 1][w - 1] - 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000000007

ll n, m, a[1005][1005], dp[1005][1005];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            char x;
            cin >> x;
            if (x == '.') a[i][j] = 1;
            else a[i][j] = 0;
        }
    dp[0][1] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (a[i][j] == 0) dp[i][j] = 0;
            else dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % M;
        }
    }
    cout << dp[n][m];
    return 0;
}


Measured memory_bytes: 16000
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n;
cin>>n;
string ans;
int c[10];
fill(c,c+5,0);
for(int i=0;i<n;i++)
{cin>>ans;
if(ans[0]=='A')c[0]++;
if(ans[0]=='W')c[1]++;
if(ans[0]=='T')c[2]++;
if(ans[0]=='R')c[3]++;
}


cout <<"AC x "<<c[0]<<endl;
cout <<"WA x "<<c[1]<<endl;
cout <<"TLE x "<<c[2]<<endl;
cout <<"RE x "<<c[3]<<endl;
}

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

using namespace std;

int main(){
  int n; cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;++i) cin >> a[i];
  sort(a.begin(),a.end());
  int tmp=0,cnt=0;
  for(int i=n-1;i>=0;--i){
    if(a[i]%2==1){
      if(tmp!=0) {
	cnt+=a[i]+tmp;
	tmp=0;
      } else tmp=a[i];
    }else cnt+=a[i];
  }
  cout << cnt/2 <<endl;
  
  return 0;
} 



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

using namespace std;

string w;
char mem;
int c=1;
int a;
bool b=1;
int j;
int k;

int main(){
    cin>>w;
    int s=w.size();
    int i=w.size()-1;
    sort(w.begin(),w.end());
    if(w.size()==1){
        cout<<"No"<<endl;
        return 0;
    }
    while(b){
        if(w[j]==w[j+1])k++;
        if(w[j]!=w[j+1]){
            if(k%2==0){
                cout<<"No"<<endl;
                return 0;
            }else{
                b=0;
            }
        }
        j++;
    }
    while(i>1){
        if(w[i]==w[i-1]){
            c++;
            i--;
            w.pop_back();
        }else{
            if(c%2==1){
            cout<<"No"<<endl;
            return 0;
            }
            c=1;
            i--;
            a++;
            w.pop_back();
        }
    }
    if(a==0&&s%2==1){
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define FOR(variable,a,b) for(variable=(a);variable<(b);variable++)

void transformAlpha(char* targetText, int count) {
    // small letter become large letter, and vice versa.
    int i;
    int index;

    FOR(i, 0, count) {
        /*if('A' <= targetText[i] && targetText[i] <= 'Z') {
            index = (targetText[i] - 'A') % 26;
            targetText[i] = 'a' + index;
            } else*/
        if('a' <= targetText[i] && targetText[i] <= 'z') {
            index = (targetText[i] - 'a') % 26;
            targetText[i] = 'A' + index;
        }
    }
    return;
}

int main(){
    // import phase
    char rawText[256];

    gets(rawText);
    
    // calclate phase
    transformAlpha(rawText, strlen(rawText));
    
    // output phase
    printf("%s\n", rawText);

    return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    vector<int> pqr(3);for (int i = 0; i < 3; ++i) cin >> pqr[i];
    sort(pqr.begin(), pqr.end());
    cout << (pqr[0] + pqr[1]) << endl;
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
int main(){
  int N, M;
  cin >> N >> M;

  vector<int> A(M);
  int sum=0;
  rep(i,M){
    cin >> A.at(i);
    sum += A.at(i);
  }

  cout << max(N-sum, -1);
  
}

Measured memory_bytes: 3668
#include <stdio.h>
int main(void)
{
	int a,b,c,d,p,q=0;
	scanf("%d %d %d %d %d",&a,&b,&c,&d,&p);
	q+=b;
	if(p>c)q+=(p-c)*d;
	if(q>a*p)q=a*p;
	printf("%d\n",q);
	return 0;
}


Measured memory_bytes: 2024
N = gets.chomp.to_i
ar = Array.new(N+1) { Array.new }
1.upto(N) do |i|
  arr = gets.chomp.split.map(&:to_i)
  arr.shift
  arr.shift
  ar[i] = arr
end

ans = Array.new(N+1, -1)
que = [[1,0]]
while !que.empty?
  n,c = que.shift
  next if ans[n] != -1 && ans[n] <= c
  ans[n] = c
  ar[n].each do |a|
    if ans[a] == -1 || ans[a] > c+1
      que.push([a,c+1])
    end
  end
end

1.upto(N) do |i|
  puts "#{i} #{ans[i]}"
end



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

using ll = long long;
#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

#define INF 1e9
const ll mod = 1e9+7;

int main(){
  string L;
  cin >> L;
  ll ans = 0, pre = 1;
  vector<ll> beki(L.size()+3, 0);
  beki[0] = 1;
  FOR(i, 1, L.size()+3){
    beki[i] = beki[i-1] * 3;
    beki[i] %= mod;
  }
  REP(i, L.size()){
    if(L[i] == '1'){
      ans += pre * beki[L.size()-i-1];
      ans %= mod;
      pre *= 2;
      pre %= mod;
    }
  }
  ans += pre;
  ans %= mod;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1280
#include <stdio.h>

typedef long long lli;

int a[200000], b[200000], n;

int main() {
	scanf("%d",&n);
	bool found=false;
	lli sum=0, mn=(1<<30);
	for(int i=0;i<n;i++) {
		scanf("%d %d",&a[i],&b[i]);
		if(a[i]!=b[i]) found=true;
		sum+=a[i];
		if(a[i]>b[i] && b[i]<mn) mn=b[i];
	}
	if(!found) {
		puts("0");
		return 0;
	}
	printf("%lld\n",sum-mn);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
const int maxn = 100005;
int f[maxn], sum[maxn];
int find(int a)
{
	if (f[a] != a)
	{
		int pre = f[a];
		f[a] = find(f[a]);
		sum[a] = sum[a] + sum[pre];
	}
	return f[a];
}
void Union(int u, int v, int rootu, int rootv, int val)
{
	f[rootu] = rootv;
	sum[rootu] = -sum[u] + val + sum[v];
}

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);
	for (int i = 1;i <= N;i++)f[i] = i,sum[i]=0;
	int u, v, rootu, rootv, dist;
	bool flag = true;
	for (int i = 1;i <= M;i++)
	{
		scanf("%d %d %d", &u, &v, &dist);
		rootu = find(u);
		rootv = find(v);
		if (rootu != rootv)
		{
			Union(u, v, rootu, rootv, dist);
		}
		else
		{
			if (sum[u] - sum[v] != dist)
				flag = false;
		}
	}
	if (flag)puts("Yes");
	else puts("No");
	return 0;
}

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

using namespace std;
typedef long long LL;
int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
const int N = 251;
int mod;
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}
void put(int x) {
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

struct node {int c, id;} sta[N * 2];
int f[N], c[N];

int add(int x, int y) {
	x += y;
	return x >= mod ? x - mod : x;
}

int dec(int x, int y) {
	x -= y;
	return x < 0 ? x + mod : x;
}

bool cmp(node a, node b) {
	if(a.c == b.c) return a.id > b.id;
	return a.c < b.c;
}

int main() {
	int n = read(); mod = read();
	int tp = 0;
	for(int i = n - 1; i >= 0; i--) {
		while(tp < 2 * n && tp * tp + i * i < n * n) tp++;
		sta[i] = node{tp, i}; 
	} tp = 0;
	for(int i = (n << 1) - 1; i >= n; i--) {
		while(tp < 2 * n && tp * tp + i * i <= 4 * n * n) tp++;
		sta[i] = node{tp, -1};
	} for(int i = n - 1; i >= 0; i--) {
		while(tp < 2 * n && tp * tp + i * i <= 4 * n * n) tp++;
		c[i] = tp;
	} sort(sta, sta + 2 * n, cmp);
	int ans = 0;
	for(int k = 0; k <= n; k++) {
		memset(f, 0, sizeof(f)); f[0] = 1;
		int u = 0, v = 0;
		for(int i = 0; i < 2 * n; i++) {
			if(sta[i].id == -1) {
				for(int j = 0; j <= _min(v, k); j++) f[j] = (LL)f[j] * _max(0, sta[i].c - u - j) % mod;
				u++;
			} else {
				for(int j = _min(v, k); j >= 0; j--) {
					if(j < k) f[j + 1] = add(f[j + 1], (LL)f[j] * _max(0, sta[i].c - u - j) % mod);
					f[j] = (LL)f[j] * _max(0, c[sta[i].id] - (n + k + v - j)) % mod;
				} v++;
			}
		} ans = k & 1 ? dec(ans, f[k]) : add(ans, f[k]);
	} put(ans), puts("");
	return 0;
}



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

int main() {
	int N;
	scanf("%d", &N);
	vector<LL> A(N, 0), B(N, 0);
	LL sumall = 0;
	for(int i=0; i<N; i++) {
		scanf("%lld", &A[i]);
		sumall += A[i];
	}
	for(int i=0; i<N; i++) {
		scanf("%lld", &B[i]);
		sumall -= B[i];
	}
	LL sum = 0, ans = 0;
	priority_queue<LL> pq;
	for(int i=0; i<N; i++) {
		sum += A[i] - B[i];
		LL cur = sumall - sum;
		ans += abs(cur);
		if(cur<=0) {
			pq.push(0);
			continue;
		}
		
		if(cur > sumall) cur = sumall;
		pq.push(-cur);
		pq.push(-cur);
		ans += pq.top();
		pq.pop();
		
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2936
#include <iostream>
#include <deque>
#include <utility>
int main() {
    int n, q;
    std::cin >> n >> q;
    std::deque<std::pair<std::string, int>> p;
    std::string s;
    int t;
    while (std::cin >> s >> t) {
        p.emplace_back(s, t);
    }
    int v = 0;
    while (!p.empty()) {
        auto e = p.front();
        p.pop_front();
        if (e.second > q) {
            e.second -= q;
            v += q;
            p.push_back(e);
        } else {
            v += e.second;
            std::cout << e.first << ' ' << v << std::endl;
        }
    }
}



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

int main(){
  int a, b, x; cin >> a >> b >> x;
  string ans = "NO";
  if(a > x) ans = ans;
  else {
    for(int i = a; i <= a+b; i++){
      if(i == x) ans = "YES";
    }
  }
  cout << ans << endl;
}

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

int main(){
  int N,M;
  cin >> N >> M ;
  if(N < 2 && M > 1){
    cout << M*(M-1)/2 << endl;
  }
  else if(M < 2 && N > 1){
    cout << N*(N-1)/2 << endl;
  }
  else if(N == 1 && M == 1){
    cout << 0 << endl;
  }
  else{
    cout << M*(M-1)/2+N*(N-1)/2 << endl;
  }
  
}


Measured memory_bytes: 256
def input_N_T():
    N_T=input().split()
    int_N_T=list(map(int,N_T))
    N=int_N_T[0]
    T=int_N_T[1]
    return [N,T]

N,T=input_N_T()

min_c,min_t=1001,1001

for i in range(N):
    c,t=input_N_T()
    if(t<=T and min(min_c,c)==c):
        min_c=c

if(min_c==1001):
    print("TLE")
    
else:
    print(min_c)

Measured memory_bytes: 3060
#include <algorithm>

#include <bitset>

#include <tuple>

#include <cstdint>

#include <cstdio>

#include <cctype>

#include <assert.h>

#include <stdlib.h>

#include <stdio.h>

#include <cassert>

#include <cfloat>

#include <climits>

#include <cmath>

#include <complex>

#include <ctime>

#include <deque>

#include <fstream>

#include <functional>

#include <iomanip>

#include <iostream>

#include <iterator>

#include <list>

#include <limits>

#include <map>

#include <memory>

#include <queue>

#include <random>

#include <set>

#include <stack>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <utility>

#include <vector>

#include <math.h>
using namespace std;
int main() {
	string S;
	cin >> S;
	int size = S.size();
	bool a = true;
	for (int i = 0; i < size; i++) {
		if (i % 2 == 0) {
			if (S.at(i) != 'R' && S.at(i) != 'U' && S.at(i) != 'D') {
				a = false;
			}
		}
		if (i % 2 == 1) {
			if (S.at(i) != 'L' && S.at(i) != 'U' && S.at(i) != 'D') {
				a = false;
			}
		}
	}
	if (a) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 1e5 + 7, M = 1e7, OO = 0x3f3f3f3f;
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin.sync_with_stdio(0);
int main()
{
int x=0,maxi=0,i,n;
string s;
cin>>n>>s;
for(i=0;i<n;++i){
    if(s[i]=='I'){
        x++;
        maxi=max(maxi,x);
    }
    else{
        x--;
        maxi=max(maxi,x);
    }
}
cout<<maxi;


    return 0;
}


Measured memory_bytes: 3596
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> products(N);
  
  int sum=0;
  for(int i=0;i<N;i++){
    cin >> products[i];
    sum+=products[i];
  }
  
  sort(products.rbegin(),products.rend());
  
  int count=0;
  for(int i=0;i<M;i++){
    if(products[i]*4*M >= sum){
      count++;
    }
  }
  
  if(count == M) cout << "Yes" << endl;
  else cout << "No" << endl;
} 

Measured memory_bytes: 256
def c_typical_stairs(N, M, A, MOD=10**9 + 7):
    a = set(A)
    way_go_up_the_stairs = [1] + [0] * (N)
    for i in range(1, N + 1):
        if i not in a:
            way_go_up_the_stairs[i] += sum([way_go_up_the_stairs[i - j - 1]
                                            for j in range(2) if i - j >= 0])
            way_go_up_the_stairs[i] %= MOD
    return way_go_up_the_stairs[N]

N, M = [int(i) for i in input().split()]
A = [int(input()) for _ in range(M)]
print(c_typical_stairs(N, M, A))

Measured memory_bytes: 13216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.begin(), a.end(), greater<int>()
#define ROT(a) a.begin(), a.begin() + 1, a.end()
#define RROT(a) a.begin(), a.end() - 1, a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
#define sz(a) a.size()
const ll MOD = 1e9 + 7;
const int MAX = 10000000;
template <typename T1, typename T2>
inline bool chmin(T1& a, T2 b)
{
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T1, typename T2>
inline bool chmax(T1& a, T2 b)
{
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
T gcd(T a, T b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
//cout << 'H' << endl;
/*--------------------------------------------*/

int main()
{
    //cout << fixed << setprecision(10)
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll X;
    cin >> X;

    cout << (X / 500) * 1000 + (X % 500) / 5 * 5 << endl;
}


Measured memory_bytes: 256
from heapq import heapify, heappop, heappush

# 次の桁の生成ルール ex. 1 -> 10, 11, 12
def next_num(n):
    if n == 0:
        return [0, 1]
    elif n == 9:
        return [8, 9]
    else:
        return [n-1, n, n+1]

K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # とりあえず 1 桁の Lunlun Number を初期値にとる
heapify(queue)

for _ in range(K-1):
    now = heappop(queue)  # 最小値を取り出す
    # 取り出した値を使って次の桁の値を生成し queue に投げる
    for next_i in next_num(now%10):
        heappush(queue, now*10 + next_i)

print(queue[0]) 

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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	string s, t;
	cin >> s >> t;
	cout << t + s << endl;
	return 0;
}

Measured memory_bytes: 256
def Eratosthenes(N): #N以下の素数のリストを返す
    #iが素数のときis_prime_list[i]=1，それ以外は0
    N+=1
    is_prime_list = [True]*N
#    is_prime_list[0], is_prime_list[1] = False, False #リストが必要なときはこの2行を有効化
#    for j in range(4,N,2): is_prime_list[j] = False
    m = int(N**0.5)+1
    for i in range(3,m,2):
        if is_prime_list[i]:
            is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,N,2) if is_prime_list[i]]
#    return is_prime_list


# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#n,m = [int(i) for i in readline().split()]
#d = [int(i) for i in readline().split()]
MOD = 10**9+7

n = int(input())
a = [int(i) for i in readline().split()]

#m = 1000000
#a = list(range(m,m+2000))

from fractions import gcd
m = a[0]
for i in a:
    m = m//gcd(m,i)*i

ans = 0
M = m%MOD
for i in a:
    ans += M*pow(i,MOD-2,MOD)%MOD

print(ans%MOD)




Measured memory_bytes: 5608
while(True):
    nums = [int(e) for e in input().split()]
    if(nums[0]==0 and nums[1]==0):break
    for i in range(nums[0]):
        for j in range(nums[1]):
            if i%2==0:
                if j%2==0:
                    print("#" ,end="")
                else:
                    print("." ,end="")
            else:
                if j%2==0:
                    print("." ,end="")
                else:
                    print("#" ,end="")
        print("")
    print("")


Measured memory_bytes: 7020
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#define ll long long
using namespace std;



int main(){
  string S,T,U;
  ll A,B;
  cin>>S>>T>>A>>B>>U;

  if(U==S) cout<<A-1<<" "<<B<<endl;
  if(U==T) cout<<A<<" "<<B-1<<endl;

    return 0;
}


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

int main() {
  string s;
  cin >> s;
  int ans = s.size();
  for (int i = 1; i < s.size(); i++) {
    if (s[i-1] != s[i]) {
      ans = min(ans, max(i, (int)s.size() - i));
    }
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

const int P = 1000000007;

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

	long long ans = 0;

	for(int i = k; i <= n + 1; ++i) {
		long long l = 1LL * i * (i - 1) / 2;
		long long r = 1LL * (n + n - i + 1) * i / 2;
		ans = (ans + r - l + 1) % P;
	}

	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 3632
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (long long i = 0; i < n; i++)
#define RREP(i, n) for (long long i = n; 0 <= i; i--)
#define FOR(i, start, end) for (long long i = start; i < end; i++)
#define FORSTEP(i, start, end, step)                                           \
    for (long long i = start; i < end; i += step)
#define RFOR(i, start, end) for (long long i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1000000007
typedef long long ll;
const long long INF32 = 2147483647;
const ll INF64        = 9223372036854775807;
using namespace std;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

vector<long long> divisor(long long N) {
    vector<long long> ans;
    for (long long i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ans.push_back(i);
            if (i != 1 && i * i != N) {
                ans.push_back(N / i);
            }
        }
    }
    ans.push_back(N);

    return ans;
}

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

    ll N;
    cin >> N;

    ll ans = 0;

    auto a = divisor(N);
    REP(i, a.size()) {
        long long b = a[i] - 1;
        if (b == 0)
            continue;
        if (N % b == N / b) {
            ans += b;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 384
let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let hs = Array.init n @@ fun _ -> Scanf.scanf "%d " Fun.id in
  let hs' = Array.make n min_int in
  for i = 1 to m do
    Scanf.scanf "%d %d\n" @@ fun a b ->
      hs'.(a - 1) <- max hs.(b - 1) hs'.(a - 1);
      hs'.(b - 1) <- max hs.(a - 1) hs'.(b - 1)
  done;
  Printf.printf "%d\n" @@
  List.fold_left ( + ) 0 @@
  List.init n @@ fun i -> if hs'.(i) < hs.(i) then 1 else 0


Measured memory_bytes: 11888
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <array>
#include <algorithm>
#include <set>
#include <iomanip>
#include <cstdio>
#include <queue>

using namespace std;

#define int long long

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

    const int def = 1000000007;
    

    int in;

    cin >> in;

    int ans = 1;

    for (int i = 1; i <= in; ++i)
    {
        ans = ans * i;
        ans = ans % def;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S],H=0,[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r();p=map(int,f[2:].split())
  if'0'==f[0]:print(g(n,E,*p))
  else:c,d,e=p;E[c]+=[(e,d)];E[d]+=[(e,c)]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))


Measured memory_bytes: 6308
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=[I() for i in range(n)]
cols=deque([inf])
i=0
while i<n:
    #print(cols)
    x=lis[i]
    if cols[0]>=x:
        cols.appendleft(x)
    else:
        cols[bisect_left(cols,x)-1]=x
        #print(bisect_left(cols,x))
    i+=1
#print(cols)
print(len(cols)-1)

    
    



Measured memory_bytes: 13852
#include <stdio.h>
#include <string.h>

#define M 1046527/* your task*/
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
  return 0;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key/* your task */; }
int h2(int key){ return 1+(key%(M-1))/* your task */; }

int find(char str[]){

    /* your task */
  long long key, i, h;
  key = getKey(str);
  for(i=0; ; i++){
    h = (h1(key)+i*h2(key)) % M;
    if(strcmp(H[h], str) == 0) return 1;
    else if(strlen(H[h]) == 0) return 0;
  }
  return 0;
}

int insert(char str[]){

    /* your task */
  long long key, i, h;
  key = getKey(str);
  for(i=0; ; i++){
    h=(h1(key) + i*h2(key)) % M;
    if(strcmp(H[h], str) == 0) return 1;
    else if( strlen(H[h]) == 0){
      strcpy(H[h], str);
      return 0;
    }
  }
  return 0;
}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){
	    insert(str);
	} else {
	    if (find(str)){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}



Measured memory_bytes: 16040
#include<stdio.h>
int main()
{
	int n,m,k;
	while(~scanf("%d %d %d",&n,&m,&k))
	{
		int s;
		s=n*m;
		if(s<k)
			printf("%d\n",s);
		else
			printf("%d\n",k);
	}
	return 0;
}

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

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

using namespace std;
using ll = long long;
int mod = 1000000007;

void solve();

int main(void){
    int H, W;
    cin >> H >> W;
    char grid[H][W];
    rep(i, H) rep(j, W) cin >> grid[i][j];
    int right_max = 0;
    bool res = true;
    rep(i, H){
        rep(j, W){
            if(grid[i][j] == '#' && j > right_max) right_max = j;
            else if(grid[i][j] == '#' && j < right_max) res = false;
        }
    }
    if(res) cout << "Possible" << endl;
    else cout << "Impossible" << endl;
    return 0;
}

void solve(){}

Measured memory_bytes: 256
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>    // bitset
#include <cctype>    // isupper, islower, isdigit, toupper, tolower
#include <cmath>     // pow
#include <cstdint>   // int64_t, int*_t
#include <cstdio>    // printf
#include <deque>     // deque
#include <iomanip>   // setprecision
#include <iostream>  // cout, endl, cin
#include <map>       // map
#include <queue>     // queue, priority_queue
#include <set>       // set
#include <stack>     // stack
#include <string>    // string, to_string, stoi
#include <tuple>     // tuple, make_tuple
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <utility>       // pair, make_pair
#include <vector>        // vector
using namespace std;

// long long gcd(long long a, long long b) { return b != 0 ? gcd(b, a % b) : a;
// }

// int binary_search(int key) {
//     int ng = -1;
//     int ok = (int)a.size();
//     while(abs(ok - ng) > 1) {
//         int mid = (ok + ng) / 2;
//         if(isOK(mid, key))
//             ok = mid;
//         else
//             ng = mid;
//     }
//     return ok;
// }

// cout << fixed << setprecision(10);
// vector<vector<int>> vec(H, vector<int>(W))    // int H*W
// int MOD = 1000000007;

int main() {
    string S;
    cin >> S;
    vector<string> week = {"SUN", "SAT", "FRI", "THU", "WED", "TUE", "MON"};
    int ans = find(week.begin(), week.end(), S) - find(week.begin(), week.end(), "SUN");
    if(ans == 0){
        ans = 7;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, Q = map(int, readline().split())
S = readline().decode("utf-8").rstrip()
qs = []
for i in range(Q):
    l, r = map(int, readline().split())
    qs.append((l - 1, r - 1))


def solve():
    acc = [0] * (N + 1)
    for i in range(1, N + 1):
        acc[i] = acc[i - 1]
        if S[i - 1 : i + 1] == "AC":
            acc[i] += 1
    for l, r in qs:
        print(acc[r] - acc[l])


if __name__ == "__main__":
    solve()


Measured memory_bytes: 19852
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000005;
int n,tot;
struct Str
{
	int a,b,c;
	inline bool operator < (const Str& b)const
	{
		if(1ll*c*b.c<=0) return c>b.c;
		if(c<0) return this->b>b.b;
		return a<b.a;
	}
}A[maxn];
inline Str read()
{
	Str ret=(Str){0,0};char ch=getchar();
	while(ch!='('&&ch!=')') ch=getchar();
	while(ch=='('||ch==')')
	{
		if(ch==')') ret.b?ret.b--:ret.a++;
		else ret.b++;
		ch=getchar();
	}
	ret.c=ret.b-ret.a;
	return ret;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		A[i]=read();
		if(A[i].a==0)
		{
			tot+=A[i].b;
			i--;n--;continue;
		}
	}
	sort(A+1,A+1+n);
	for(int i=1;i<=n;i++)
	{
		tot-=A[i].a;
		if(tot<0)
		{
			printf("No\n");
			return 0;
		}
		tot+=A[i].b;
	}
	printf("%s\n",tot?"No":"Yes");
	return 0;
}

Measured memory_bytes: 7480
/**
  @file c.cpp
  @title C - Divide the Problems
  @url https://atcoder.jp/contests/abc132/tasks/abc132_c
**/

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, N) for (int i = 0; i < (N); ++i)

int main() {
  int i;

  int N;
  cin >> N;

  vector<LL> d(N + 1, 0);
  for (i = 1; i <= N; i++) {
    cin >> d[i];
  }
  sort(ALL(d));

  if (d[N / 2] == d[(N / 2) + 1]) {
    cout << "0" << endl;
  } else {
    cout << d[(N / 2) + 1] - d[N / 2] << endl;
  }

  return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#define MAX 100

int adj[MAX][MAX];/*隣接行列*/
int d[MAX];/*発見時刻*/
int f[MAX];/*終了時刻*/
int flg[MAX];/*ノード訪問したかどうか*/
int time=0;

void dfs(int u,int n){
	
	flg[u]=1;
	d[u]=++time;
	
	for(int i=0;i<n;i++){
		if(adj[u][i] && !flg[i]){/*ノードuから到達可能かつ未訪問*/
			dfs(i,n);
		}
	}
	f[u]=++time;
	
	return;
	
}

int main(){
	int n,i,j;
	int x,y,z;
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++){
		flg[i]=0;
		for(j=0;j<n;j++)
			adj[i][j]=0;
	}
	
	for(i=0;i<n;i++){
		scanf("%d %d",&x,&y);
		for(j=0;j<y;j++){
			scanf("%d",&z);
			adj[x-1][z-1]=1;
		}
	}
	
	for(i=0;i<n;i++)
		if(!flg[i])
			dfs(i,n);
	
	
	for(i=0;i<n;i++)
		printf("%d %d %d\n",i+1,d[i],f[i]);
	
	return 0;
	
}


Measured memory_bytes: 2748
def main():
    n = int(input())
    h = list(map(int, input().rstrip().split(' ')))
    print(min_cost(n, h))

def min_cost(n, h):
    cost = [10 ** 10] * n
    cost[0] = 0
    for i in range(n):
        if i + 1 < n:
            cost[i + 1] = min(cost[i] + abs(h[i] - h[i+1]), cost[i + 1])
        if i + 2 < n:
            cost[i + 2] = min(cost[i] + abs(h[i] - h[i+2]), cost[i + 2])
    return cost[-1]



if __name__ == '__main__':
    main()

Measured memory_bytes: 13908
#include <stdio.h>

int main(void) {
  int i, j, n, cnt = 0;
  scanf("%d", &n);
  char st[n + 10];
  scanf("%s", st);
  bool t[n], s[n];
  for(i = 0; i < n; ++i) s[i] = (st[i] == 'o' ? true : false);
  bool b, bt1, bt2;
  for(j = 0; j < 4; ++j) {
    t[0] = j & 1, t[1] = j & 2;
    for(i = 2; i < n; ++i) {
      t[i] = (s[i - 1] && t[i - 1]) || (!s[i - 1] && !t[i - 1]);
      if(t[i]) t[i] = t[i - 2];
      else t[i] = !t[i - 2];
    }
    b = true;
    bt1 = (s[n - 1] && t[n - 1]) || (!s[n - 1] && !t[n - 1]);
    bt2 = (t[0] && t[n - 2]) || (!t[0] && !t[n - 2]);
    if(bt1 != bt2) b = false;
    bt1 = (s[0] && t[0]) || (!s[0] && !t[0]);
    bt2 = (t[n - 1] && t[1]) || (!t[n - 1] && !t[1]);
    if(bt1 != bt2) b = false;
    if(b) {
      for(i = 0; i < n; ++i) printf("%c", t[i] ? 'S' : 'W');
      return 0;
    }
  }
  printf("-1");
  return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<int,int> P;
typedef pair<int,P> PP;
int a[32]={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};
int main()
{
	int k;
	cin>>k;
	cout<<a[k-1]<<endl;
	return 0;
}

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

using namespace std;

const int MAX_N = 100005;

vector<int> G[MAX_N];
int p[MAX_N];
bool visit[MAX_N];

int main()
{
    int n, m;
    cin >> n >> m;
    rep(i,n){
        cin >> p[i];
        --p[i];
    }
    rep(i,m){
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].push_back(b), G[b].push_back(a);
    }
    int ans = 0;
    queue<int> que;
    rep(i,n){
        if(visit[i]) continue;
        set<int> st = {i};
        visit[i] = true;
        que.push(i);
        while(!que.empty()){
            int u = que.front();
            que.pop();
            for(const int v : G[u]){
                if(!visit[v]){
                    st.insert(v);
                    visit[v] = true;
                    que.push(v);
                }
            }
        }
        for(const int e : st){
            ans += (st.find(p[e]) != st.end());
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 10880
#include <bits/stdc++.h>
using  namespace std;
typedef long long ll;
#define RAP(i, n) for(ll i=0;i<(n);i++)
#define FOR(i, a, b) for(ll i=(a);i<(b);i++)

#include <iostream>
#include <vector>
using namespace std;

//重複順列
vector<ll> buf;
void permutation(ll i, const ll size, const ll range_start, const ll range_end)
{
    if (i == size) {
      // ここで所望の作業を行う
      for(ll itr:buf){
        cout << itr;
      }
    }
    else{
        for(ll j = range_start; j <= range_end; ++j){
            buf[i] = j;
            permutation(i + 1, size, range_start, range_end);
        }
    }
}
vector<ll> H;
bool check(vector<ll> G, ll index){
  ll test = H[index];
  if(G.size()==0){
    return true;
  }
  for(int itr:G){
    if(test<=H[itr]){
      return false;
    }
  }
  return true;
}
int main(void)
{
 ll n, m, a, b, ans = 0;
 cin >> n >> m;
 H.resize(n+1);
 vector<vector<ll>> G(n+1);
 RAP(i, n){
   cin >> H[i+1];
 }
 RAP(i,m){
   cin >> a >> b;
   G[a].push_back(b);
   G[b].push_back(a);
 }
 for(ll i=1;i<=n;i++){
   if(check(G[i], i)){
     ans++;
   }
 }
 
 cout << ans << endl;
 return 0;
}


Measured memory_bytes: 9924
x=int(input())
if 400<=x<=599:
  print("8")
elif 600<=x<=799:
  print("7")
elif 800<=x<=999:
  print("6")
elif 1000<=x<=1199:
  print("5")
elif 1200<=x<=1399:
  print("4")
elif 1400<=x<=1599:
  print("3")
elif 1600<=x<=1799:
  print("2")
else:
  print("1")

Measured memory_bytes: 9184
#include <bits/stdc++.h>
#define ll long long
#define eps 1e-7
using namespace std;
#define pi acos(-1)

struct Node { int key; Node* le, * ri, * p; };
Node* root, * NIL;
void insert(int k) {
	Node* y = NIL, * x = root;
	Node* z;
	z = new(Node);
	z->key = k;
	z->le = NIL, z->ri = NIL;
	while (x != NIL) {
		y = x;
		if (z->key < x->key) x = x->le;
		else x = x->ri;
	}
	z->p = y;
	if (y == NIL) root = z;
	else {
		if (z->key < y->key) y->le = z;
		else y->ri = z;
	}
}
void preorder(Node* u) {
	if (u != NIL) {
		printf(" %d", u->key);
		preorder(u->le);
		preorder(u->ri);
	}
}
void inorder(Node* u) {
	if (u != NIL) {
		inorder(u->le);
		printf(" %d", u->key);
		inorder(u->ri);
	}
}

int main() {
	int n, i, k;
	string com;
	cin >> n;
	while (n--) {
		cin >> com;
		if (com == "insert") cin >> k, insert(k);
		else if (com == "print") inorder(root), cout << endl, preorder(root), cout << endl;
	}
}


Measured memory_bytes: 26728
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[200020],h[200020],c[200020],h1[200020],f[200020],b[200020],pre[200020],ans,b1[200020],b2[200020],b22[200020];
ll lowbit(ll x)
{
	return x&-x;
}
void add(ll x,ll y)
{
	for(;x<=n;x+=lowbit(x))
		c[x]=max(c[x],y);
}
ll ask(ll x,ll y)
{
	ll ans=-1;
	while(y>=x && y)
	{
		if(y-lowbit(y)>=x)
		{
			ans=max(ans,c[y]);
			y-=lowbit(y);
		}
		else
		{
	//		if(b[y]<y1)
			ans=max(ans,f[b[b22[y]]]);
			y--;
		}
//		cout<<y<<endl;
	}
	return ans;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
		h1[i]=h[i],b[h[i]]=i;
	}
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(h1+1,h1+n+1);
	for(int i=1;i<=n;i++)
		b2[h1[i]]=i,b22[i]=h1[i];
	priority_queue <ll> q;
	for(int i=n;i>=1;i--)
	{
		while(!q.empty() && q.top()>h[i])
		{
			pre[b[q.top()]]=i;
			q.pop();
		}
		q.push(h[i]);
	}

	for(int i=1;i<=n;i++)
	{
		f[i]=ask(b2[h[pre[i]]],b2[h[i]])+a[i];
		ans=max(ans,f[i]);
		add(b2[h[i]],f[i]);		
//		cout<<endl<<f[i]<<' '<<c[i]<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 17520
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lb(x) (x&-(x))
const int N = 101010;

long long num[100];
int main(){
	int n;
	num[0]=2;
	num[1]=1;
	for(int i=2;i<=86;i++)
	{
		num[i]=num[i-1]+num[i-2];
	}
	cin>>n;
	cout<<num[n]<<endl;




    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdlib>
#define manx 150005
using namespace std;

int top,s[1000];
void push(int x)
{
    s[++top]=x;
}

int pop()
{
    top--;
    return s[top+1];
}

int main()
{
    int a,b;
    top=0;
    char c[100];
    while(~scanf("%s",c))
    {
        if(c[0]=='+')
        {
            a=pop();
            b=pop();
            push(a+b);
        }
        else if(c[0]=='-')
        {
            a=pop();
            b=pop();
            push(b-a);
        }
        else if(c[0]=='*')
        {
            a=pop();
            b=pop();
            push(a*b);
        }
        else
            push(atoi(c));
    }
    printf("%d\n",pop());
    return 0;
}



Measured memory_bytes: 3220
#include <stdio.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define min(l,r) (l<r?l:r)

int main(){
    int n;scanf("%d",&n);
    int a[105]; rep(i,n) scanf("%d",a+i);

    int color[10]={0};
    rep(i,n) color[min(a[i]/400,8)]++;
    int ans=0;
    rep(i,8) if(color[i]) ans++;
    if(color[8]==n) ans=1;

    printf("%d ",ans);
    if(color[8]==n) ans--;
    ans+=color[8];
    printf("%d\n",ans);
}

Measured memory_bytes: 1732
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=100000+10,L=100000;

int n,o[N];

int main() {
	n=read();
	for (int i=1;i<=n;++i) ++o[read()];
	int ans=0;
	for (int i=1;i<L;++i) ans=max(ans,o[i-1]+o[i]+o[i+1]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3908
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ul unsigned long long int
#define ld long double
#define f(t) for(ll i =0;i<t;i++)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define inf 4e18
#define EPS 1e-3
#define PI 3.1415926535897932385
#define display(v) f(v.size())cout << v[i]<<" "
const double h = 1e-6;
const int MAX_  = 200005;
#define all(v) v.begin(),v.end()

inline ll mul(ll a, ll b){ return (a * 1ll * b) % MOD; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += MOD; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > MOD) c -= MOD; return c; }
ll sqr(ll x)
{
    return x*x;
}
 //////////////////////*********CODE***********/////////////////////
 //////////////////////////////////////////////////////////////////


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k;   cin>>n>>k;
    vector<pair<int,int> >v;
    v.pb({1,2});
    for(int i=3;i<=n;i++){
        v.pb({2,i});
    }
    int mx = (n-2) + ((n-2)*(n-3))/2;
    int mn = (n-2);
    if(k > mx){
        cout << -1;
        return 0;
    }
    int rem = mx - k;

    if(rem!=0){
    for(int i =3;i<=n;i++){
        v.pb({i,1});
        rem--;
        if(rem==0)break;
        for(int j = i+1;j<=n;j++){
            v.pb({i,j});rem--;
            if(rem==0){
                break;
            }
        }
        if(rem==0)break;
    }
    }
    cout << v.size()<<"\n";
    for(int i =0;i<(int)v.size();i++){
        cout << v[i].ff << " " << v[i].ss << "\n";
    }
    

    return 0;
}
    


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using vll = vector<ll> ;
#define all(v) v.begin(),v.end()


vll eratosthenes_sieve(ll N){
	vll table(N+1,0);
	vll prime;
	for(int i=2;i<=N;++i){
		if(table[i]==0){
			prime.push_back(i);
			for(int j=i+i;j<=N;j+=i) table[j]=1;
		}
	}
	return prime;
}

int main(){
  int N;cin>>N;
  vll prime = eratosthenes_sieve(55555);
  vll ans{2};
  int i=1;
  while(ans.size()<N){
    while(prime[i]%5!=2){
      ++i;
    }
    ans.push_back(prime[i]);
    ++i;
  }
  rep(i,N) cout << ans[i] << " ";
  cout <<endl;
}

Measured memory_bytes: 768
import java.util.*;
class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    Map<Integer,Integer> m = new HashMap<>();
    long sum = 0;
    for(int i = 0; i < N; i++){
      int A = sc.nextInt();
      m.put(A, m.getOrDefault(A,0)+1);
      sum += A;
    }
    StringBuilder ans = new StringBuilder();
    int Q = sc.nextInt();
    for(int i = 0; i < Q; i++){
      int B = sc.nextInt();
      int C = sc.nextInt();
      if(!m.containsKey(B)){
        ans.append(sum).append("\n");
        continue;
      }
      int num = m.get(B);
      sum -= (long) num*B;
      sum += (long) num*C;
      m.put(C,m.getOrDefault(C,0)+num);
      m.remove(B);
      ans.append(sum).append("\n");
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 65980