akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
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; }
const long long INF = 1LL<<60;

// 入力
int N;
long long W, weight[110], value[110]; // 品物の個数は 100 個なので少し余裕持たせてサイズ 110 に

// DPテーブル
long long dp[110][100100] = {0};

int main() {
    cin >> N >> W;
    for (int i = 0; i < N; ++i) cin >> weight[i] >> value[i];
    
    // DPループ
    for (int i = 0; i < N; ++i) {
        for (int sum_w = 0; sum_w <= W; ++sum_w) {
            
            // i 番目の品物を選ぶ場合
            if (sum_w - weight[i] >= 0) {
                dp[i+1][sum_w]= dp[i][sum_w - weight[i]] + value[i];
            }
            
            // i 番目の品物を選ばない場合
            chmax(dp[i+1][sum_w], dp[i][sum_w]);
        }
    }
    
    // 最適値の出力
    cout << dp[N][W] << endl;
}

Measured memory_bytes: 79360
//http://arc071.contest.atcoder.jp/tasks/arc071_d
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000010;
const long long  base = 1e9+7;

long long f[maxn],n;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    f[1]=n;
    f[2]=n*n%base;
    int sum=0;
    for (int i=3;i<=n;i++) {
        if (i>3) sum = (sum+f[i-3])%base;
        f[i]=(f[i-1] + (n-1)*(n-1)%base + sum + (n-1 - (i-3))) % base;
    }
    cout<<f[n];
}


Measured memory_bytes: 8064
def gcd(a, b):
    if  b == 0:
        return a
    else:
        return gcd(b, a % b)

def gcd_list(a):
    x = a[0]
    for i in range(len(a)):
        x = gcd(a[i], x)
    return x
        

n, k = map(int, input().split())
A = list(map(int, input().split()))

ans = 'IMPOSSIBLE'
A.sort()
if A[-1] >= k and (A[-1] - k) % gcd_list(A) == 0:
    ans = 'POSSIBLE'

print(ans)


Measured memory_bytes: 14480
/**
 * @author: Mackenzie
**/
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define pb push_back
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
#ifdef LOCAL
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#else
    fastIO;
#endif
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b && a != c || (b == c && b != a) || (a == c && a != b))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

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

  int K;  std::cin >> K;
  std::string S;  std::cin >> S;
  if (S.length() <= K)
    std::cout << S << "\n";
  else {
    for (int i = 0; i < K; ++i)
      std::cout << S[i];
    std::cout << "...\n";
  }

  return 0;
}


Measured memory_bytes: 3636
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <set>

#define ll long long
#define pll pair<ll, ll>

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

const int INF = 1111111111;
const double EPS = 1e-9;

using namespace std;

const int N = 222222;
int n, m, k;
int a[N], b[N];

void init()
{
	cin >> n >> m >> k;
	rep(i, n) cin >> a[i];
	rep(i, m) cin >> b[i];
}

void solve()
{
	int sumA = 0;
	int cntA = 0;
	rep(i, n)
	{
		if (sumA + a[i] <= k)
		{
			sumA += a[i];
			cntA++;
			continue;
		}
		break;
	}

	int sumB = 0;
	int cntB = 0;
	rep(i, m)
	{
		if (sumB + b[i] + sumA <= k)
		{
			sumB += b[i];
			cntB++;
			continue;
		}
		break;
	}

	int ans = cntA + cntB;

	while (cntA >= 0)
	{
		cntA--;
		sumA -= a[cntA];

		reps(i, cntB, m)
		{
			if (sumA + sumB + b[i] <= k)
			{
				sumB += b[i];
				cntB++;
				continue;
			}
			break;
		}

		ans = max(ans, cntA + cntB);
	}

	cout << ans << endl;
}

int main()
{
	init();
	solve();
}


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

using namespace std;

long long int  n,s, m,k,ans,b,d,f,s1,s2,s3,w,a,c,z2,z1,z3,ans1;
string  j,t,g,k2,k3;
bool ww=false,wwr=false;
set <int> ss;

char e1,e2;

int main() {
  cin>>n>>m;
cout<<n-m+1;
	return 0; 
}

Measured memory_bytes: 256
//#include <GOD>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define len length	
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define freo freopen("output.txt","w",stdout)
#define frei freopen("input.txt","r",stdin)

const ll inf=1e18;
const ll mod=1e9+7;
const ll maxn=5e3+10,maxp=10110;

ll n,ans;
vector <ll> ve1,ve2,ve3,ve4;

int main(){
	FAST_IO;
	cin>>n;
	for(int i=0;i<n;i++){
		ll x,y;
		cin>>x>>y;
		ve1.pb(x+y);
		ve2.pb(x-y);
		ve3.pb(y-x);
		ve4.pb(-x-y);
	}
	sort(ve1.begin(),ve1.end());
	sort(ve2.begin(),ve2.end());
	sort(ve3.begin(),ve3.end());
	sort(ve4.begin(),ve4.end());
	ans=ve1[n-1]-ve1[0];
	ans=max(ans,ve2[n-1]-ve2[0]);
	ans=max(ans,ve3[n-1]-ve3[0]);
	ans=max(ans,ve4[n-1]-ve4[0]);
	cout<<ans<<endl;
}


Measured memory_bytes: 9688
# 2019/07/17
# AtCoder Grand Contest 021 - A
# For the answer: 
# 1. 桁分割、桁数Count
# 2-1. 上位桁から9以外を探索
# 2-2. 9以外があれば、その1つ上桁を-1
# 2-3. ただし先頭の場合は自身を-1
# 3. (桁数-1)*9 + 上位桁-1

# Input
n = int(input())

# 1.
wn = n
ketalist = list()
defans = 0
while wn > 0:
    remn = wn % 10
    defans = defans + remn
    ketalist.append(remn)
    wn = int(wn / 10)

# 2. 
ketalist.reverse()
allflg = False
for i in range(len(ketalist)):
    if ketalist[i] < 9:
        if i == 0:
            tgtnum = ketalist[i] - 1
        else:
            tgtnum = ketalist[i-1] - 1
        break
    # Case all 9:
    if i == len(ketalist) - 1:
        allflg = True

# 3.
if len(ketalist) > 1 and allflg == False:
    if ketalist[0] == 1:
        ans = (len(ketalist) - 1) * 9
    else:
        ans = (len(ketalist) - 1) * 9 + tgtnum
elif len(ketalist) > 1 and allflg == True:
    ans = len(ketalist) * 9
else:
    ans = n

# Output
print(max(ans, defans))


Measured memory_bytes: 3064
#![allow(unused_imports)]
use std::io::{ self, Write };
use std::str::FromStr;
use std::cmp::{ min, max };
use std::collections::{ BinaryHeap, VecDeque };

#[allow(unused_macros)]
macro_rules! trace {
    ($var:expr) => {
        let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($var), $var);
    };
    ($($args:expr),*) => {
        let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($($args),*), ($($args),*));
    };
}

fn main() {
    let mut sc = Scanner::new();
    let h: i32 = sc.cin();
    let w: i32 = sc.cin();
    let n: usize = sc.cin();
    let mut xs = vec![0 as usize; n]; for i in 0..n { xs[i] = sc.cin(); }

    let mut f = vec![vec![0 as usize; w as usize]; h as usize];

    let dx = vec![0, 1, 0, -1];
    let dy = vec![1, 0, -1, 0];
    let mut d = 0;
    let mut x: i32 = 0;
    let mut y: i32 = 0;
    for i in 0..n {
        for _ in 0..xs[i] {
            f[x as usize][y as usize] = i + 1;
            x += dx[d];
            y += dy[d];
            if x < 0 || y < 0 || x >= h || y >= w || f[x as usize][y as usize] != 0 {
                x -= dx[d];
                y -= dy[d];
                d = (d + 1) % 4;
                x += dx[d];
                y += dy[d];
            }
        }
    }

    for i in 0..h {
        for j in 0..(w - 1) {
            print!("{} ", f[i as usize][j as usize]);
        }
        println!("{}", f[i as usize][(w - 1) as usize]);
    }
}

#[allow(dead_code)]
struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn reserve(&mut self) {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        self.reserve();
        match self.buffer.pop_front().unwrap().parse::<T>() {
            Ok(a) => a,
            Err(_) => panic!("parse err")
        }
    }
    fn get_char(&mut self) -> char {
        self.reserve();
        let head = self.buffer[0].chars().nth(0).unwrap();
        let tail = String::from( &self.buffer[0][1..] );
        if tail.len()>0 { self.buffer[0]=tail } else { self.buffer.pop_front(); }
        head
    }
}


Measured memory_bytes: 4352
a,s['~~'],t['~~'];main(b,i){for(;i=~scanf("%d,%*d%*c%[\n]",&a,s);b-=i+2)s[a]|=b,t[a]++;for(;a=++i<1e4;)s[i]>2&&printf("%d %d\n",i,t[i]);}

Measured memory_bytes: 0
#include <stdio.h>
#include <string.h>
 
int main(void) {
	char s[201], p[101], tmp[101];
	int slen, plen;
	int i, j, flag;
	
	gets(s);
	gets(p);
	
	slen = strlen(s);
	plen = strlen(p);
	
	strcpy(tmp, s);
	strcat(s, tmp);
	
	for (i = 0; i < slen; i++){
		flag = 0;
		if (p[0] == s[i]){
			for (j = 0; j < plen; j++){
				if (p[j] != s[i+j])	break;
				if (j == plen-1) flag = 1;
			}
		}
		if (flag) break;
	}
	
	if (flag) printf("Yes\n");
	else printf("No\n");
	
	return 0;
}

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

int main() {
  int a, b, c, k; cin >> a >> b >> c >> k;
  int answer = a + b + c - max({a, b, c});
  int num = max({a, b, c});
  
  for (int i = 0; i < k; i++) num *= 2;
  answer += num;
  
  cout << answer << endl;
}

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


ull gcd(ull a,ull b){
	if(!b) return a;
	return gcd(b,a%b);
}


int main(){
	int h,w;
	char c;
	cin >> w >> h >> c;
	
	rep(i,0,h){
	    rep(j,0,w){
	        if((i == 0 || i == h-1 ) && (j == 0 || j == w-1)){
	            cout << "+";
	        }
	        else if(i == 0 || i == h-1){
	            cout << "-";
	        }
	        else if(j == 0 ||j == w-1){
	            cout << "|" ;
	        }
	        else if(i == h/2 && j == w/2){
	            cout << c;
	        }
	        else{
	            cout << "." ;
	        }
	    }
	    cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3108
n, m = gets.split(" ").map(&:to_i)
xs = gets.split(" ").map(&:to_i)
xs.sort!

hoge = []

xs.each.with_index do |x,i|
  if i != 0
    hoge << {val: (x - xs[i-1]).abs, index: i}
  end
end

if hoge == []
  puts 0
  exit
end

hoge.sort!{|a,b| a[:val] <=> b[:val]}.reverse!
if n == 1
  puts (xs[0] - xs[-1]).abs
  exit
else
  use = hoge.take(n-1)
  inds = use.sort{|a,b| a[:val] <=> b[:val]}.map{|a| a[:index]}.sort
end

group = []
before = 0
inds.each do |i|
  current = xs[before...i]
  group << current
  before = i
end
group << xs[inds[-1]..-1]

count = group.reduce(0) do |a,e|
  a+=(e[0]-e[-1]).abs
end

puts count

Measured memory_bytes: 43648
//前置き
#pragma region

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>

using namespace std;

typedef  long long ll;

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)

#pragma endregion

//関数定義
#pragma region 
//偶数 ->　true :: 奇数　-> false
bool EVEN(ll a){
    return a%2-1;
}

//最大公約数
ll gcd(ll a, ll b) {  
    if (!b)  
        return a;  
    return gcd(b, a%b);  
}  

//最小公倍数
ll lcm(ll a, ll b) {  
    return a*b/gcd(a,b);  
} 

#pragma endregion

int main(){
    string s;
    cin >> s;
    int cnt1 = 0, cnt2 = 0;
    REP(i, s.size()){
        if(s[i] == '0') cnt1++;
        else cnt2++;
    }

    cout << s.size() - abs(cnt1 - cnt2) << endl;
}




Measured memory_bytes: 512
#include<stdio.h>
int main() {
  int i, j, c_num=0, c_max=0, count[5]={0,0,0,0,0}, min[6], MAX=0;
  
  for(i=0; i<5; i++) {
  	scanf("%d", &min[i]);
	for(j=0; (min[i] % 10 )!=0; j++) {
      min[i] = min[i] + 1;
      count[i] = count[i] + 1;
    }
  }
  
  for(i=0; i<5; i++) {
    if(c_max < count[i]) {
      c_max = count[i];
      c_num = i;
    }
  }
  
  min[c_num] = min[c_num] - c_max;
  
  for(i=0; i<5; i++) {
    MAX = MAX + min[i];
  }
  
  printf("%d", MAX);
    
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x)(x).begin(), (x).end() // 昇順ソート
#define rall(v)(v).rbegin(), (v).rend() // 降順ソート
#define INF 1 LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair < ll, ll >
#define F first
#define S second
const int MOD = 1000000007;
template < class T > bool chmax(T & a,const T & b) { if (a < b) { a = b; return true; } return false; }
template < class T > bool chmin(T & a,const T & b) { if (a > b) { a = b; return true; } return false; }
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main() {
    LL N,K;cin >> N >> K;
    vector<LL> A(N);
    rep(i,N)cin >> A[i];
    rep(i,N-K){
        if(A[i] < A[K+i])cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

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

/* define const */

/* finish defineing const */

long n,a,b;
long x[100010];

int main()
{
  cin >> n >> a >> b;
  for (int i = 0; i < n; i++) cin >> x[i];
  // input

  long sum = 0;
  //  cout << ":"<< endl;
  for (int i = 1; i < n; i++) {
    if ((x[i]-x[i-1])*a < b) {
      sum += (x[i]-x[i-1])*a;
    }
    else
      sum += b;
    //    cout << sum << " ";
  }
  ///  cout << endl;
  cout << sum << endl;
}


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

const int mod = 1e9 + 7;
const int MAX = 1e5 + 5;
vector<int> v[MAX];
ll dp[MAX][2];

ll dfs(int i, int par, int c) {
	if(dp[i][c] != -1) {
		return dp[i][c] % mod;
	}
	dp[i][c] = 1;
	for(auto u:v[i]) {
		if(u == par) continue;
        dfs(u, i, 0);
		if(c == 1) {
			dp[i][c] = (dp[i][c] * dp[u][0])% mod;
		}
		else {
            dfs(u, i, 1);
			dp[i][c] = (dp[i][c] * (dp[u][0] + dp[u][1])) % mod; 
		}
	}
	return dp[i][c] % mod;
}

int main() {
	int n; cin >> n;
	for(int i = 0; i < MAX; i++) {
		dp[i][0] = -1;
		dp[i][1] = -1;
	}	
	for(int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	cout << (dfs(1, -1, 0) + dfs(1, -1, 1)) % mod << endl;
    return 0;
}

Measured memory_bytes: 18968
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
map<int, int> mp;
bool judge(int num) {
    while(num > 0) {
        if(mp[num%10]==1) return false;
        num /=10;
    }
    return true;
}
int main() {
    int n, k; cin >> n >> k;
    rep(i, k) {
        int d; cin >> d;
        mp[d] = 1;
    }
    for(int i=n;i<=10*n;i++) {
        if(judge(i)) {
            cout << i;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
    if (n == 1)
        return false;
    bool ans = true;
    for(int i = 2; i*i<=n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return ans;
}


bool a[100001];
int  b[100001];

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
 
    for (int i = 2; i <= 100001; i++) {
        if (i % 2 == 1)
            if (isPrime(i) && isPrime((i+1)/2))
                a[i] = true;
    }
    
    b[1] = a[1];
    for (int i = 2; i <=100001; i++)
        b[i] = b[i-1] + (int)a[i];
    
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        
        cout << b[r] - b[l-1] << '\n';
    }
    
    return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int MOD=1e9+7;
const long double Pi=acos(-1);
using  P=pair<ll,ll>;
ll gcd(ll a,ll b){//aとbの最大公約数を返す//計算量は0(log(max(a,b))
  if(a%b==0){return b;}
  else{return gcd(b,a%b);}
}
ll lcm(ll a,ll b){//aとbの最小公倍数を返す//計算量は0(log(max(a,b))
  return a*b/gcd(a,b);
}
ll pow(ll x,ll y){//x^yを返す//計算量は0(log(y))
  ll tmp=x,res=1;
  while(y){
    if(y%2){res=res*tmp%MOD;}
    y>>=1;
    tmp=tmp*tmp%MOD;
  }
  return res;
}
ll nature(ll a){//絶対値を返す
  if(a>=0){return(a);}
  else{return(-1*a);}
}
ll prime(ll a){//素数なら1を返す//計算量は0(sqrt(a))
  if(a==2){return 1;}
  else if(a%2==0 || a==1){return 0;}
  for(ll i=3;i*i<=a;i+=2){if(a%i==0){return 0;}}
  return 1;
}
vector<int> Z;
void z_algorithm(string str){//計算量はO(str.size())
  Z.resize(str.size());
  Z.at(0)=str.size();
  int m=1,n=0;
  while(m<(int)str.size()){
    while(m+n<(int)str.size()&&str.at(n)==str.at(m+n)){n++;}
    Z.at(m)=n;
    if(n==0){
      m++;
      continue;
    }
    int k=1;
    while(k+Z.at(k)<n){
      Z.at(m+k)=Z.at(k);
      k++;
    }
    m+=k;
    n-=k;
  }
}
vector<vector<int>> vec;
vector<vector<int>> now;
bool dfs(int i){
    int ii=now.at(i).at(0);
    if(ii==-1){return false;}
    if(now.at(ii).at(0)==i){return true;}
    else{return false;}
}
int main(){
    int N;
    cin>>N;
    vec.resize(N,vector<int>(N-1));
    now.resize(N,vector<int>(0));
    vector<int> enemy(N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            int a;
            cin>>a;
            vec.at(i).at(j)=a-1;
            if(j==0){
                now.at(i).push_back(a-1);
            }
        }
        enemy.at(i)=0;
    }
    ll count=0;
    ll day=0;
    //countはN(N-1)/2まで
    while(count<N*(N-1)/2){
        unordered_map<int,int> mp;
        int memo=count;
        day++;
        for(int i=0;i<N;i++){
            //cout<<count<<" "<<i<<endl;
            if(dfs(i) && mp[i]==0 && mp[now.at(i).at(0)]==0 && now.at(i).at(0)!=-1){
                count++;
                int a=i;
                int b=now.at(i).at(0);
                enemy.at(a)++;
                enemy.at(b)++;
                mp[a]=1;
                mp[b]=1;
                //cout<<a<<" "<<b<<"   "<<enemy.at(a)<<" "<<enemy.at(b)<<endl;
                if(enemy.at(a)<N-1){
                    //cout<<a<<" "<<b<<" "<<enemy.at(a)<<endl;
                    now.at(a).at(0)=vec.at(a).at(enemy.at(a));
                }
                else{
                    now.at(a).at(0)=-1;
                }
                if(enemy.at(b)!=N-1){
                    //cout<<" "<<a<<" "<<b<<" "<<enemy.at(b)<<endl;
                    now.at(b).at(0)=vec.at(b).at(enemy.at(b));
                }
                else{
                    now.at(b).at(0)=-1;
                }
            }
        }
        if(memo==count){
            cout<<-1<<endl;
            return 0;
        }
        mp.clear();
    }
    cout<<day<<endl;
}

Measured memory_bytes: 7644
#include <iostream>
#include <cmath>

using namespace std;

int main() {
  int n, l;
  cin >> n >> l;
  int ans_i = 1;
  int min_taste = 1000000000;
  for (int i = 1; i <= n; ++i) {
    if (abs(l+i-1) < min_taste) {
      min_taste = abs(l+i-1);
      ans_i = i;
    }
  }
  int sum = 0;
  for (int i = 1; i < ans_i; ++i) {
    sum += l+i-1;
  }

  for (int i = ans_i+1; i <= n; ++i) {
    sum += l+i-1;
  }
  cout << sum << endl;
}


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

#define gap " "
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ok cout<<"ok"<<endl
#define dbg(x) cout<<(#x)<<" is "<<x<<endl
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}

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

const int N=100009;

int main()
{
  int t,l,r,cnt=0,mx=0,n,i;
  scanf("%d %d",&n,&l);

  for(i=2; i<=n; i++)
  {
    scanf("%d",&r);
    if(r<=l)
    {
    	cnt++;
    }
    else
    {
    	mx=max(mx,cnt);
    	cnt=0;
    }
    l=r;
  }
  mx=max(mx,cnt);
  printf("%d\n",mx);
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef std::vector<vector<int> > vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pi> vpi;
#define debugone(x) cerr << #x << " " << x << "\n"; cerr.flush();
#define debugtwo(x) cerr << #x << "-------------" << "\n";for(auto &it: x) cerr << it << " ";cerr << "\n"; cerr.flush();
#define debugthree(x, i, j) cerr << #x << "------------" << "\n";cerr << "from " << i << " to " << j << "\n";for(ll k=i; k<=j; k++) cerr << x[k] << " ";cerr << "\n"; cerr.flush();
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
 
const ll mod = 1e9 + 7;
const ll inf = 1e11 + 5;
const int MaxN = 2e5 + 5;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n;
	cin >> n;
	int a[2 * n];
	for(int i = 0; i < 2 * n; i++){
		cin >> a[i];
	}
	sort(a, a + 2 * n);
	int ans = 0;
	for(int i = 0; i < 2 * n; i += 2){
		ans += a[i];
	}
	cout << ans << endl;
	return 0;
}


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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define ALL(v) (v).begin(), (v).end()
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO  cout << "NO"  << endl
#define No  cout << "No"  << endl

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;


void solve()
{
    int N; cin >> N;
    vi V(N); REP(i, N) cin >> V[i];
    vi C(N); REP(i, N) cin >> C[i];
    int ans = 0;
    REP(i, N)
    {
        if(V[i] - C[i] > 0) ans += V[i] - C[i];
    }
    cout << ans << endl;
} 
    
int main() 
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

Measured memory_bytes: 256
/*
　　　∫ ∫ ∫
　　　ノヽ
　　（＿　 ）
　（＿　　　 ）
（＿＿＿＿＿＿ ）
　ヽ(´･ω･)ﾉ　
　　 |　 /
　　 UU
*/
#pragma region macro
#include <bits/stdc++.h>
typedef long long int64;
typedef long double ld;
using namespace std;
using P = pair<int64, int64>;
typedef vector<int> vi;
const int MOD = (int)1e9 + 7;
const int64 INF = 1LL << 62;
const int inf = 1<<30;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = s; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
#define mp make_pair
#define bn '\n'
template <typename T>
ostream& operator<<(ostream& os, vector<T> &V){
    int N = V.size();
    REP(i,N){
        os << V[i];
        if (i!=N-1) os << " ";
    }
    os << "\n";
    return os;
}
template <typename T,typename S>
ostream& operator<<(ostream& os, pair<T,S> const&P){
    os << "(";
    os << P.first;
    os << " , ";
    os << P.second;
    os << ")";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T> &S){
    auto it=S.begin();
    while(it!=S.end()){
        os << *it;
        os << " ";
        it++;
    }
    os << "\n";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, deque<T> &q){
    for(auto it=q.begin();it<q.end();it++){
        os<<*it;
        os<<" ";
    }
     os<<endl;
    return os;
}
vector<pair<int,int>> dxdy = {mp(0,1),mp(1,0),mp(-1,0),mp(0,-1)};
#pragma endregion
//fixed<<setprecision(10)<<ans<<endl;

int N;
ld dfs(int i, int j, int k, vector<vector<vector<ld>>>& dp){
    if(not (i or j or k)) return 0;
    if(dp[i][j][k]) return dp[i][j][k];

    ld res = (ld)N/(i+j+k);

    if(i) res += dfs(i-1,j+1,k,dp) * i/(i+j+k);
    if(j) res += dfs(i,j-1,k+1,dp) * j/(i+j+k);
    if(k) res += dfs(i,j,k-1,dp) * k/(i+j+k);
    dp[i][j][k] = res;
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    vector<vector<vector<ld>>> dp(N+1,vector<vector<ld>>(N+1,vector<ld>(N+1,0)));
    
    vector<int> cnt(4,0);
    int a;
    REP(i,N){
        cin >> a;
        cnt[a]++;
    }
    ld ans=dfs(cnt[3],cnt[2],cnt[1],dp);
    cout << fixed<<setprecision(10)<<ans<<endl;
}

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

using namespace std;

typedef long long int ll;

int main()
{
    map<ll,ll> mp;
    for(int i=1 ; i<=100 ; i++)
    {
        for(int j=1 ; j<=100 ; j++)
        {
            for(int k=1 ; k<=100 ; k++)
            {
                ll ka = (i+j+k)*(i+j+k) + i*i + j*j + k*k;
                if(ka%2==0)
                {
                    ka/=2;
                    mp[ka]++;
                }
            }
        }
    }
    int n;
    cin >> n;
    for(int i=1 ;i<=n ; i++)
        cout << mp[i] << "\n";
    return 0;
}


Measured memory_bytes: 6052
#include<bits/stdc++.h>
using namespace std;
long long N,A,B,C,D,ans;
int main()
{
    scanf("%d%d%d%d%d",&A,&B,&C,&D,&N);
	ans=min(min(4*A,2*B),C);
    cout<<min(ans*N,(N/2*D+N%2*ans))<<"\n";
    return 0;
}

Measured memory_bytes: 256
s = input()
ans = [0] * len(s)
pt = [0]

i = 0
for i in range(len(s)-1):
    if s[i] != s[i+1]:
        pt.append(i+1)
pt.append(len(s))

for i in range(0, len(pt)-2, 2):
    w = (pt[i+1] - pt[i]) // 2
    ans[pt[i+1]] += w
    ans[pt[i+1]-1] += (pt[i+1] - pt[i]) - w

    w = (pt[i+2] - pt[i+1]) // 2
    ans[pt[i+1]-1] += w
    ans[pt[i+1]] += (pt[i+2] - pt[i+1]) - w

print(*ans)


Measured memory_bytes: 10224
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int n; cin>>n;
    int ac=0,wa=0,tle=0,re=0;
    rep(i,n){
        string s; cin>>s;
        if(s=="AC") ac++;
        else if(s=="WA") wa++;
        else if(s=="TLE") tle++;
        else re++;
    }
    cout<<"AC x "<<ac<<endl;
    cout<<"WA x "<<wa<<endl;
    cout<<"TLE x "<<tle<<endl;
    cout<<"RE x "<<re<<endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
using namespace std;
 
typedef int ll;
 
#define int long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define endl '\n'
 
typedef pair<int,int>pii;
typedef pair<int,pair<int,int> > piii;
 
const int mod=1e9+7;
 
int POWER[65];
int power(int a, int b) {int ret=1;while(b) {if(b&1) ret*=a;a*=a;if(ret>=mod) ret%=mod;if(a>=mod) a%=mod;b>>=1;}return ret;}
int inv(int x) {return power(x,mod-2);}
 
void precompute() {
	POWER[0]=1;
	for(int i=1;i<63;i++) POWER[i]=POWER[i-1]<<1LL;
}
 
int gcd(int a, int b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}
 
ll main() {
	// freopen("Task.in", "r", stdin);freopen("Task.out", "w", stdout);

	int x, k, d;
	cin>>x>>k>>d;

	x=abs(x);
	int num = x/d;

	if(k<num) {
		cout<<x-(k*d)<<endl;
		return 0;
	}

	int lef = k-num;
	if(lef%2) {
		cout<<abs(x%d-d)<<endl;
	} else {
		cout<<x%d<<endl;
	}
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
#define P pair<int,int>
const int MOD=1e9+7;
const int INF=2e9;
const double PI=acos(-1);


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

    string s;
    cin >> s;
    ll k;
    cin >> k;
    ll n=s.size();
    int cnt=1;
    vector<ll> c;
    rep(i,n-1) {
        if (s[i]==s[i+1]) ++cnt;
        else {
            c.push_back(cnt);
            cnt=1;
        }
    }
    if (cnt>1) c.push_back(cnt);
    int m=c.size();
    ll ans=0;
    if (s[0]!=s[n-1]) {
        rep(i,m) {
            ans+=ll(c[i]/2)*k;
        }
    } else if (m>2) {
        repr(i,1,m-1) {
            ans+=ll(c[i]/2)*k; 
        }
        ans+=ll(c[0]/2)+ll(c[m-1]/2)+ll((c[0]+c[m-1])/2)*(k-1);
    } else {
        ans=(k*n)/2;
    }
    cout << ans << endl;


    
    return 0;   
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int K=50;
int n,f[101],a[101],b[101];
LL ans;
bool check(LL x) {
    for (int i=1;i<=n;i++) {
	memset(f,0,sizeof(f));
	f[a[i]]=1;
	for (int j=K;j>=1;j--)
	    if (x&(1ll<<j))
		for (int k=0;k<=K;k++)
		    if (f[k]) f[k%j]=1;
	if (!f[b[i]]) return 0;
    }
    return 1;
}
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) scanf("%d",&b[i]);
    ans=(1ll<<(K+1))-1;
    if (!check(ans)) {
	printf("-1\n");
	return 0;
    }
    for (int i=K;i>=0;i--) {
	ans^=(1ll<<i);
	if (!check(ans)) ans^=(1ll<<i);
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned int uint;
typedef pair<int,int> pii;
//-------------------------------------------------------------------LYYY↓
namespace LYYY{
	int rd()
	{
		int s=0;char c=getchar();int f=1;
		while(c<48||c>57)
		{
			if(c==45) f=-1;
			c=getchar();
		}
		while(c>=48&&c<=57) s=(s<<3)+(s<<1)+(c^48),c=getchar();
		return s*f;
	}
	LL rdl()
	{
		LL s=0;char c=getchar();int f=1;
		while(c<48||c>57)
		{
			if(c==45) f=-1;
			c=getchar();
		}
		while(c>=48&&c<=57) s=(s<<3)+(s<<1)+(c^48),c=getchar();
		return s*f;
	}
	void wt(int x)
	{
		if(x>=10) wt(x/10);
		putchar(x%10+48);
	}
	void WT(int x)
	{
		if(x<0) x=-x,putchar(45);
		wt(x);
	}
	void wtl(LL x)
	{
		if(x>=10) wtl(x/10);
		putchar(x%10+48);
	}
	void WTL(LL x)
	{
		if(x<0) x=-x,putchar(45);
		wtl(x);
	}
}using namespace LYYY;
//-------------------------------------------------------------------bianliang↓
char ss[111111];
//-------------------------------------------------------------------hanshu↓
//-------------------------------------------------------------------main()↓
int main()
{
	int N=rd(),ans=0;
	scanf("%s",ss+1);
	for(int i=1;i<=N;++i)if(ss[i]!=ss[i-1]) ++ans;
	WT(ans);
}

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

int asdf(int g, int h){
    int j;
    while(h!=0){
        j=g%h;
        g=h;
        h=j;
    }
    return g;
}
int main(){
    long long a,b,c,d;
    cin >> a >> b >> c >> d;
    long long ans=b-a+1;
    long long c1=a/c;
    long long c2=b/c;
    if(a%c==0)c2+=1;
    long long d1=a/d;
    long long d2=b/d;
    if(a%d==0)d2+=1;
    long long z =c*d/asdf(d,c);
    long long e1=a/z;
    long long e2=b/z;
    if(a%z==0)e2+=1;
    long long count=(c2-c1)+(d2-d1)+(e1-e2);
    cout << ans-count << endl;
}

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

using namespace std;

#define int long long

const int   N   = 5e5 + 1;
const int   B   = 1e8 + 1;

typedef pair<int,int>   ii;

int qpow(int a,int exp,int mod) {
    if(exp < 0) exp = mod - 1 + exp;
    int ans = 1;
    while (exp) {
        if(exp & 1) ans = ans * a % mod;
        a = a * a % mod;  exp >>= 1;
    }
    return ans;
}

void add(int &a,int b,int mod) {
    a += b;
    if(a >= mod)a -= mod;
    if(a < 0)   a += mod;
}

int mod[2];
int n, f[N];
int H[N][2];
string S;

void process(int t)   {
    for(int i = 1 ; i <= n ; ++i)   {
        H[i][t] = H[i - 1][t];
        if(S[i - 1] == '+') add(H[i][t], qpow(B,f[i],mod[t]),mod[t]);
        if(S[i - 1] == '-') add(H[i][t],-qpow(B,f[i],mod[t]),mod[t]);
    }
}

map<ii,int> mp;

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

    cin >> n >> S;

    for(int i = 0 ; i < n ; ++i)    {
        f[i + 1] = f[i];
        if(S[i] == '>') f[i + 1]++;
        if(S[i] == '<') f[i + 1]--;
    }

    mod[0] = 1e9 + 7;
    mod[1] = 1e9 + 9;

    process(0);
    process(1);

    mp[ii(H[n][0],H[n][1])] = 1;

    int ans = 0;

    for(int i = 1 ; i <= n ; ++i)   {
        ans += mp[ii(H[i][0],H[i][1])];
        int res0 = H[n][0] * qpow(B,f[i],mod[0]) + H[i][0];
        int res1 = H[n][1] * qpow(B,f[i],mod[1]) + H[i][1];
        res0 %= mod[0]; res1 %= mod[1];
        mp[ii(res0,res1)]++;
    }

    cout << ans << endl;
}


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

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

	int ans = 0;

	for (int i = 0; i < N; i++) {
		int cnt = 0;

		for (char c = 'a'; c <= 'z'; c++) {
			if (S.substr(0, i).find(c) == string::npos) {
			}
			else if (S.substr(i).find(c) == string::npos) {
			}
			else{
				cnt += 1;
			}
		}
		ans = max(ans, cnt);
	}
	cout << ans;
}


Measured memory_bytes: 256
def main():
    import math
    def generate_primes(num):
        if num == 1: return []
        primes = list(range(2, num + 1))
        i, p = 0, 1
        while p <= math.sqrt(num):
            if primes[i] != 0:
                p = primes[i]
                primes = [prime if (prime % p != 0 or prime == p) else 0 for prime in primes]
            i += 1
        return set([p for p in primes if p != 0])

    primes = generate_primes(100000)
    ans = [0] * 50001
    for j in range(1, 50001):
        i = 2 * j - 1
        if i in primes and (i + 1) // 2 in primes:
            ans[j] = ans[j - 1] + 1
        else:
            ans[j] = ans[j - 1]
    q = int(input())
    for _ in range(q):
        l, r = list(map(lambda x: (int(x) + 1) // 2, input().split()))
        print(ans[r] - ans[l - 1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 8184
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

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

	string S;
	cin >> S;
	int A = S[0]-'0';
	int B = S[1]-'0';
	int C = S[2]-'0';
	int D = S[3]-'0';
	for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			for(int k=0; k<2; k++){
				int tmp = A;
				if(i==0) tmp += B;
				else tmp -= B;
				if(j==0) tmp += C;
				else tmp -= C;
				if(k==0) tmp += D;
				else tmp -= D;

				if(tmp == 7){
					cout << A;
					if(i==0) cout << "+";
					else cout << "-";
					cout << B;
					if(j==0) cout << "+";
					else cout << "-";
					cout << C;
					if(k==0) cout << "+";
					else cout << "-";
					cout << D << "=7" << endl;
					return 0;
				}
			}
		}
	}

	return 0;
}



Measured memory_bytes: 256
def solve():
    base = []
    for a, s in zip(A[::-1], S[::-1]):
        #print(f'a: {a}, s: {s}')
        #for i, y in enumerate(base):
        #    print('base{:d} {:3d}: {:05b}'.format(i, y, y))
        x = a
        for y in sorted(base, reverse=True):
            x = min(x, x ^ y)
        if x:
            if s == "0":
                base.append(x)
            else:
                return 1
    return 0


t = int(input())
for _ in range(t):
    n = int(input())
    *A, = map(int, input().split())
    S = input()
    #print(f'A: {A}, S: {S}')
    print(solve())
    #print('-'*32)


Measured memory_bytes: 9100
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pb(x) push_back(x);
#define mp(x,y) make_pair(x,y)
#define mem(dp,a) memset(dp,a,sizeof dp);
#define all(a) a.begin(),a.end()
#define sall(a) sort(all(a))
#define X first
#define Y second
typedef long long int ll;
typedef pair<ll,ll> pp;

#define debug(x) cout << #x << " :: "<< x <<"\n";
#define debug2(x,y) cout << #x << " :: "<< x << "\t" << #y << " :: " << y << "\n";
#define debug3(x,y,z) cout << #x << " :: "<< x << "\t" << #y << " :: " << y << "\t" << #z << " :: " << z << "\n";
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree< pp , null_type,less< pp >, rb_tree_tag,tree_order_statistics_node_update>

ll power(ll b, ll exp){
    ll res = 1;
    while(exp > 0){
        if(exp % 2){
            res = 1LL * res * b % mod;
        }
        b = 1LL * b * b % mod;
        exp /= 2;
    }
    return res;
}

vector<ll> p,r;

void build(ll n)    {
    for(ll i=0;i<=n;i++)    {
        p[i]=i;
        r[i]=0;
    }
}

ll find_set(ll v)   {
    if( p[v]==v )
        return v;
    return p[v]=find_set(p[v]);
}

void union_set(ll a,ll b)   {
    a=find_set(a);
    b=find_set(b);
    if( a!=b )  {
        if( r[a]<r[b] )
            swap(a,b);
        p[b]=a;
        if( r[a]==r[b] )
            r[a]++;
    }
}

int main()
{
    boost
    ll n,m;
    cin >> n >> m;
    p.assign(n+1,0);
    r.assign(n+1,0);
    build(n);
    for(ll i=0;i<m;i++) {
        ll x,y;
        cin >> x >> y;
        union_set(x,y);
    }
    map<ll,ll> ma;
    for(ll i=1;i<=n;i++)    {
        find_set(i);
        ma[p[i]]++;
    }
    ll ans=0,prev=0;
    set<ll> s;
    for(auto it:ma) {
        s.insert(it.Y);
    }
    for(auto it:s)  {
        ans+=(it-prev);
        prev=it;
    }
    cout << ans ;
    return 0;
}


Measured memory_bytes: 18676
#include<cstdio>
#include<algorithm>
#include<cmath>
const int MaxN=200010,L=99999999;
int N;
struct Point{
	int x,y;
	void read(){scanf("%d%d",&x,&y);}
	bool operator<(const Point&p)const{return x<p.x;}
}p1,p2,P[MaxN];
int f[MaxN];
int main(){
	p1.read();
	p2.read();
	scanf("%d",&N);
	for(int i=0;i<N;i++)P[i].read();
	if(p1.x>p2.x){
		p1.x=L-p1.x;
		p2.x=L-p2.x;
		for(int i=0;i<N;i++)P[i].x=L-P[i].x;
	}
	if(p1.y>p2.y){
		p1.y=L-p1.y;
		p2.y=L-p2.y;
		for(int i=0;i<N;i++)P[i].y=L-P[i].y;
	}
	int n=0;
	for(int i=0;i<N;i++)
		if(P[i].x>=p1.x&&P[i].x<=p2.x&&P[i].y>=p1.y&&P[i].y<=p2.y)P[n++]=P[i];
	std::sort(P,P+n);
	int l=0;
	f[0]=-1;
	for(Point*p=P;p<P+n;p++){
		if(p->y>f[l])f[++l]=p->y;
		else*std::lower_bound(f,f+l,p->y)=p->y;
	}
	double dis=(p2.x-p1.x+p2.y-p1.y)*100.0+(5*acos(-1)-20)*l;
	if(l>p2.x-p1.x||l>p2.y-p1.y)dis+=5*acos(-1);
	printf("%.15lf\n",dis);
}

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

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N, A, B; cin >> N >> A >> B;
  ll prev;
  ll ans = 0;
  for (ll i = 1; i <= N; i++) {
    ll x; cin >> x;
    if (i == 1) {
      prev = x;
    }else {
      ans += min((x - prev) * A, B);
      prev = x;
    }
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 3624
import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
     String[] nyu=sc.nextLine().split(" ");

//     String nyu=sc.nextLine();
int A=Integer.parseInt(nyu[0]);
int B=Integer.parseInt(nyu[1]);
int C=Integer.parseInt(nyu[2]);
//int D=Integer.parseInt(nyu);



//StringBuffer sb = new StringBuffer(nyu);
//		String dst = sb.reverse().toString();

//     String nyu2=sc.nextLine();
//int E=Integer.parseInt(nyu2);



//double A=Double.parseDouble(nyu[0]);
//double B=Double.parseDouble(nyu[1]);
/*
switch(C){
case 7:
case 5:
case 3:
System.out.println("YES") ;
break;
default:
System.out.println("NO") ;

break;
}
*/

//int res=Math.min((A*B),C);

//for(String tem:nyu){
//if(tem.equals("1"))res++;
//}
//int res=0;
//for(int i=0;i<300;i++){
//if(num[i]==1)res=i;
//}

//char[] c = nyu.toCharArray();


//System.out.println(nyu+"-"+line_r_2+"-"+nyu2+"-"+line_r_1);



if(B-A==C-B){
//double res=Math.ceil((AB)/2);

System.out.println("YES");
//}else if((C-B)<A){
//System.out.println("safe");

}else{
System.out.println("NO");

}




	}
}

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

using namespace std;

int main() {
  int k, n;
  cin >> k >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int mx = 0;
  for (int i = 1; i < n; i++) {
    mx = max(mx, a[i] - a[i - 1]);
  }
  mx = max(mx, k - a[n - 1] + a[0]);
  cout << k - mx << endl;
  return 0;
}


Measured memory_bytes: 1024
N, K = map(int, input().split())
A = list(map(int, input().split()))
balls = {}
for num in A:
  if num in balls:
    balls[num] += 1
  else:
    balls[num] = 1
# print(balls)
l = list(balls.values())
l.sort()
# print(l)
answer = 0
if K < len(l):
  for i in range(0, len(l) - K):
    answer += l[i]
print(answer)


Measured memory_bytes: 34172
#include <bits/stdc++.h>
using namespace std;
int N, M, a[50], b[50];

bool coneCheck(int r, int s, int t){
int d=1,c[N]={}; c[s]=1;
while(d){ d=0;
   for(int i=0; i<M; i++){
     if((c[a[i]]^c[b[i]])&&(i!=r)){ c[a[i]]=1; c[b[i]]=1; d=1; }
   }
}
if(c[t]==1){ return true; }else{ return false; }
}

bool bridCheck(int e){
for(int i=0; i<N-1; i++){ for(int j=i+1; j<N; j++){ 
   if(!coneCheck(e,i,j)){return true;}
} }
return false;
}

int main(){
cin >> N >> M;
for(int i=0; i<M; i++){ scanf("%d", &a[i]); scanf("%d", &b[i]); }

int c=0;
for(int i=0; i<M; i++){ if(bridCheck(i)){c++;} }
cout << c;
}

Measured memory_bytes: 256
n=int(input())
*a,=map(int, input().split())
def invr(x):
    if len(x)<=1:
        return x,0
    m=len(x)
    x1=x[:m//2]
    x2=x[m//2:]
    x11,res1=invr(x1)
    x22,res2=invr(x2)
    rx=[];res=res1+res2
    l=0;r=0
    while l<m//2 and r<m-(m//2):
        if x11[l]<=x22[r]:
            rx.append(x11[l])
            l+=1
        else:
            rx.append(x22[r])
            r+=1
            res+=m//2-l
    rx+=x11[l:]
    rx+=x22[r:]
    return rx,res

def f(m):
    a2=[(ai>=m)*2-1 for ai in a]
    a3=[0]
    for ai in a2:
        a3.append(a3[-1]+ai)
    _,r=invr(a3)
    return n*(n+1)//2-r>=((n+1)*n//2)//2



mx=max(a)+1;mn=min(a)
while mx-mn>1:
    md=(mx+mn)//2
    r=f(md)
    if r:
        mn=md
    else:
        mx=md
print(mn)





Measured memory_bytes: 227496
using System;
using System.Collections.Generic;

public class Hello{
    public static void Main(){
        int n = int.Parse(Console.ReadLine());
        var t = new Tuple<string, int, int>[n];
        
        string[] input;
        for(int i=0; i<n; i++){
            input = Console.ReadLine().Split(' ');
            t[i] = new Tuple<string, int, int>(input[0],int.Parse(input[1]),i+1);
        }
        Array.Sort(t, rule);
        for(int i=0; i<n; i++) Console.WriteLine(t[i].Item3);
    }
    public static int rule(Tuple<string, int, int> x, Tuple<string, int, int> y){
        int z = x.Item1.CompareTo(y.Item1);
        if(z != 0) return z;
        else return - (x.Item2 - y.Item2);
    }
}


Measured memory_bytes: 13408
#include <bits/stdc++.h>
using namespace std;
#define popcnt(a) __builtin_popcount(a)
#define FastIO() ios::sync_with_stdio(false), cin.tie(0);
#define IO() freopen("palindrome.in","rw",stdin)
#define error(args...)                       \
{                                            \
    cerr<<"LINE "<<__LINE__;                 \
    string _s = #args;                       \
    replace(_s.begin(), _s.end(), ',', ' '); \
    stringstream _ss(_s);                    \
    istream_iterator<string> _it(_ss);       \
    err(_it, args);                          \
    cerr<<endl;                              \
}
void err(istream_iterator<string> it)
{
} 
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
  cerr<<' '<< *it << " = " << a ;
  err(++it, args...);
} 
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 1e6+9, M = (1<<31), OO = 0x3f3f3f3f;
int arr[N];
int main()
{
  int n,mx=0,cnt=0;
  scanf("%d",&n);
  for(int i=0;i<n;++i) scanf("%d",arr+i);
  for(int i=1;i<n;++i)
  {
    if(arr[i-1]>=arr[i]) cnt++;
    else
    {
      mx=max(mx,cnt);
      cnt=0;
    }
  }
  mx=max(mx,cnt);
  printf("%d\n",mx);  
  #ifdef _LOCAL_DEFINE
  cerr << (double)clock() * 1.0 / CLOCKS_PER_SEC << endl;
  #endif
  return 0; 
}

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

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define fst first
#define snd second

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];

    for(int i = 0; i < n; i++)
    {
        if(!(a[i] & 1) && (a[i] % 3 != 0 && a[i] % 5 != 0))
        {
            cout << "DENIED";
            return 0;
        }
    }
    cout << "APPROVED";

    return 0;
}


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

int main(){
    int a[5];
    for(int i = 0; i < 5; i++) cin >> a[i];
    int sum = 0, MAX = 0;
    for(int i = 0; i < 5; i++){
        int tmp = (a[i] + 9) / 10 * 10;
        sum += tmp;
        MAX = max(MAX, tmp - a[i]);
    }
    cout << sum - MAX << endl;
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = []
for i in range(n):
    t = na()
    u = t[0] - 1
    k = t[1]
    v = [x-1 for x in t[2:]]
    g.append(v)
dist = [-1] * n
que = deque()
dist[0] = 0
que.append(0)
while que:
    #print(que)
    v = que.popleft()
    for nv in g[v]:
        if dist[nv] != -1: continue
        dist[nv] = dist[v] + 1
        que.append(nv)

for i in range(n):
    print(i+1, dist[i])



Measured memory_bytes: 9040
N = int(input())

#v = []#[500, 300, 200]
v = [float(s) for s in raw_input().split()]

for i in range(len(v) - 1):
    v.sort(reverse=True)
    _mean = (v.pop() + v.pop())/2.0
    v.append(_mean)

print(v[0])

Measured memory_bytes: 2568
class Box:
    def __init__(self, num=1, mayred=False):
        self.num = num
        self.mayred = mayred

n, m = (int(s) for s in input().strip().split(' '))
boxes = [Box() for _ in range(n)]
boxes[0].mayred = True
for _ in range(m):
    x, y = (int(s) for s in input().strip().split(' '))
    boxes[x-1].num -= 1
    boxes[y-1].num += 1
    if boxes[x-1].mayred == True:
        boxes[y-1].mayred = True
        if boxes[x-1].num == 0:
            boxes[x-1].mayred = False
print(len(list(filter(lambda b: b.mayred, boxes))))


Measured memory_bytes: 21232
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    while(scanf("%d",&n),n) {
        char c[2];
        int vote[26]={0};
        int rest=n;
        bool OK=0;
        for(int i=0;i<n;i++) {
            scanf("%s",c);
            if(OK) continue;
            vote[c[0]-'A']++;
            rest--;
            int fs=-1,sc=-1,top=-1;
            for(int j=0;j<26;j++) {
                if(fs<=vote[j]) sc=fs,fs=vote[j],top=j;
                else if(sc<vote[j]) sc=vote[j];
            }
            if(sc+rest<fs) {printf("%c %d\n",'A'+top,i+1);OK=1;}
        }
        if(!OK) printf("TIE\n");
    }
}

Measured memory_bytes: 3200