akhauriyash/Code-Regression huggingface dataset:
/******************************************************/
/******************************************************/
/**                                                  **/
/**            BISMILLAHIR RAHMANIR RAHIM            **/
/**         REAZ AHAMMED CHOWDHURY - reaziii         **/
/**  Department of Computer Science and Engineering  **/
/*         INSTITUTE OF SCIENCE AND TECHNOLOGY       **/
/**                                                  **/
/******************************************************/
/******************************************************/



#include<bits/stdc++.h>
#define sc(x)        scanf("%lld",&x)
#define pcase(x)     printf("Case %d: ",x++)
#define pn           printf("\n")
#define fri(f)       for(int i=0;i<f;i++)
#define frj(f)       for(int j=0;j<f;j++)
#define reset(x,e)   memset(x,e,sizeof(x))
#define all(x)       x.begin(),x.end()
#define input        freopen("input.txt","r",stdin);
#define output       freopen("output.txt","w",stdout)
#define infi         INT_MAX
#define m_v          3000000
#define pii          pair<int,int>
#define pch          pair<char,char>
#define pll          pair<ll,ll>
#define mgraph       map<int,vector<int> >
#define mp           make_pair
#define pb           push_back
#define clr(x)       memset(x,0,sizeof(x))
#define frx(x,y)     for(int x=0;x<y;x++)
#define ff           first
#define ss           second
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
bool checkbitt(ll num, int pos);
ll setbitt(ll num, ll pos);
ll resetbitt(ll num, int pos);
void read(int *aa, int sz) {fri(sz) scanf("%d", (aa + i));}
void read(ll *aa, int sz) {fri(sz) scanf("%lld", (aa + i));}
void read(ll *aa, int s, int e) {for (int i = s; i < s + e; i++)scanf("%lld", (aa + i));}
void read(int *aa, int s, int e) {for (int i = s; i < s + e; i++)scanf("%d", (aa + i));}
const ll mod =       1e9 + 7;
const ll N =     1e6 + 10;

//.................___Start from here___.................//
//.................._____________________................//

int n;
int dp[N][5];
int a[N], b[N], c[N];
int A = 1, B = 2, C = 3;
int solve() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}


	for (int i = n; i >= 1; i--) {
		dp[i][A] = max(dp[i + 1][B], dp[i + 1][C]) + a[i];
		dp[i][B] = max(dp[i + 1][A], dp[i + 1][C]) + b[i];
		dp[i][C] = max(dp[i + 1][A], dp[i + 1][B]) + c[i];
	}

	cout << max(dp[1][A], max(dp[1][B], dp[1][C])) << endl;



	return 0;
}
int main() {
// #ifndef ONLINE_JUDGE
// 	input;
// 	output;
// #endif
// #ifdef ONLINE_JUDGE
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0);
// #endif
	int cs = 1;
	int cn = 1;
	//cin>>cs;
	while (cs--) {
		solve();

	}
}


bool checkbitt(ll num, int pos) {return (num >> pos) & 1;}
ll setbitt(ll num, ll pos) {return (1 << pos) | num;}
ll resetbitt(ll num, int pos) {if (!checkbitt(num, pos)) return num; else return (1 << pos)^num;}



Measured memory_bytes: 6764
import java.util.*;

public class Main {
	public static void main(String[] args) {
		int i;
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		sc.close();
		int cnt=15-s.length();
		for(i=0;i<s.length();i++){
			if(s.charAt(i) == 'o') cnt++;
		}
		System.out.println(cnt>=8?"YES":"NO");
	}
}

Measured memory_bytes: 21844
n=int(input())
a=list(map(int, input().split()))
col=[0]*9
for i in range(n):
    j=min(8, a[i]//400)
    col[j]+=1
zero=0
cnt=0
for c in range(len(col)-1):
    if col[c]==0:
        zero+=1
    else:
        cnt+=1
m=max(cnt,1)
M=cnt+col[-1]
print(m,M)

Measured memory_bytes: 8976
#include<bits/stdc++.h>
#define mx 10e7
#define ll long long int
using namespace std;
//int sum_of_digit (int a){
//    int x=a, r,sum=0;
//    while(a!=0){
//        r=a%10;
//        dsum+=r;
//        a/=10;
//    }
//   return sum;
//}
int main(){
ll a,b,x,cnt=0;
cin>>a>>b;
if(a<10){
    b+=100*(10-a);
}
 cout<<b<<endl;
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;
//vector<int> sosuu(1,2);

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

int main(){
    int n;
    cin>>n;
    vector<int> ans(0);
    int i=1;
    int flag=n;
    while(flag){
        int num=5*i+1;
        if(sosuu_hantei(num)){
            ans.push_back(num);
            flag--;
        }
        i++;
    }
    for(int i=0;i<n;i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};
 int main(){
   ll n,k ,l ; cin>>n>>k>>l ;
   UnionFind af(n),bf(n) ;
   rep(i,k){
     ll a,b ;cin>>a>>b ;
     a-- ;b-- ;
     af.unite(a,b) ;
   }
   rep(i,l){
     ll a,b ;cin>>a>>b ;
     a-- ;b-- ;
     bf.unite(a,b) ;
   }
   vector<pair<P,ll>> A(n) ;
   rep(i,n){
     A[i].fi.fi=af.find(i) ;
     A[i].fi.se=bf.find(i) ;
     A[i].se=i ;
     // cout<<af.find(i)<<" "<<bf.find(i)<<endl;
   }
   sort(A.begin(),A.end()) ;
   vector<pair<ll,vector<ll>>> B(n) ;
   rep(i,n){
     B[i].fi=0 ;
   }
   ll j=0 ;
   rep(i,n){
     if(i==0 || ((A[i].fi.fi==A[i-1].fi.fi) &&(A[i].fi.se==A[i-1].fi.se))){
     B[j].fi ++ ;
     B[j].se.pb(A[i].se) ;
     }
     else{
       j++ ;
       B[j].fi ++ ;
       B[j].se.pb(A[i].se) ;
     }
   }
   ll ans[n] ;
   rep(i,n){
     if(B[i].fi==0) break ;
   for(auto u : B[i].se ){
   ans[u]=B[i].fi ;
   }
   }

  rep(i,n){
    if(i==n-1)cout<<ans[i]<<endl ;
    else cout<<ans[i]<<" " ;
  }
   return 0;
  }

Measured memory_bytes: 21136
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <vector>
#include <list>
#include <queue>
#include <stack>

using namespace std;


int main() {
	double r;
	cin >> r;
	cout << 2 * r * 3.14 << endl;

	return 0;
}


Measured memory_bytes: 3808
#include <bits/stdc++.h>
using namespace std;
string s1, s2;
deque<char> ans;
int dp[3005][3005];
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> s1 >> s2;
int n=s1.size(), m=s2.size();
for (int i=1;i<=n;i++){
	for (int j=1;j<=m;j++){
		if (s1[i-1]==s2[j-1]){
			dp[i][j]= max(max(dp[j][j-1], dp[i-1][j]), dp[i-1][j-1]+1);
		}
		else {
			dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
		}
	}
}
if (dp[n][m]==0) cout << " ";
else {
	while (dp[n][m]>0) {
		if (dp[n][m] == dp[n-1][m]) n--;
		else if (dp[n][m] == dp[n][m-1]) m--;
		else {
			n--; m--; ans.push_front(s1[n]);
		}
	}
	for (int i=0;i<ans.size();i++) cout << ans[i];
}
return 0;
}

Measured memory_bytes: 35456
#include<bits/stdc++.h>
#define mod 1000000007
#define eps 1e-9
#define PI 3.14159265358979323846
#define F first
#define S second
#define ll long long
#define pb push_back
#define mp make_pair
#define Fr(i,a,b) for(int i=a;i<=b;i++)
#define RF(i,a,b) for(int i=a;i>=b;i--)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pii>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        int n,yy;
        cin>>n>>yy;
        vi a;
        vvi b;
        b.resize(n);int x,y;
        Fr(i,0,n-2){
            cin>>x>>y;x--;y--;
            b[x].pb(y);
            b[x].pb(x);
        }
        a.resize(n,0);
        Fr(i,0,yy-1){
            cin>>x>>y;
            x--;
            a[x]+=y;
        }
        queue<pii>q;
        vector<bool>visit(n,false);
        q.push(mp(0,a[0]));
        visit[0]=true;
        while(!q.empty()){
            x=q.front().F;
            y=q.front().S;
            q.pop();
            for(int i=0;i<b[x].size();i++){
                if(visit[b[x][i]]==false){
                    visit[b[x][i]]=true;
                    a[b[x][i]]=y+a[b[x][i]];
                    q.push(mp(b[x][i],a[b[x][i]]));
                }
            }
        }
       Fr(i,0,n-1){
            cout<<a[i]<<" ";
       }
       cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 14208
import java.util.Scanner;
public class Main {
  
  public static void main (String[] args) {
    Scanner scan = new Scanner(System.in);
    int length = Integer.parseInt(scan.next());
    String str = scan.next();
    String key = "ABC";
    int cnt = 0;
    
      for (int i = 0; i + (key.length() - 1) < str.length() ; i++){
        	if (str.substring(i, i + key.length()).equals(key)) {
              cnt++;
            }
      }
    
    System.out.println(cnt);
  }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
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; }
const ll INF = 1LL << 60;
int main(){
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    map<int, int> mp;
    rep(i,n) mp[a[i]] = i+1;

    for (auto p : mp){
        cout << p.second << " ";
    }

    return 0;
}

Measured memory_bytes: 5888
#include <iostream> // C++の入出力
#include <stdio.h> // C の入出力
#include <algorithm> // sort などのアルゴリズム
#include <string.h> // C の文字列用
#include <ctype.h> // C の文字種用
#include <string> // C++の文字列
using namespace std;
const int Max=10000000;
bool prime[Max];
int main(void){
    int in,i;
    for(int i=0;i<Max;i++)prime[i]=true;
    prime[1]=false;
    for(int i=2;i<Max;i++){
        if(prime[i]){
            for(int s=i*2;s<=Max;s+=i)prime[s]=false;
        }
    }
    while(1){
        cin>>in;
        if(in==0)break;
        for(i=in;i>0;i--){
            if(prime[i]==true&&prime[i-2]==true&&prime[i-6]==true&&prime[i-8]){
                cout<<i<<"\n";
                break;
            }
        }
        
    }
    return 0;
}

Measured memory_bytes: 10928
#include <iostream>
#include <unordered_map>
#include <utility>
#include <algorithm>

using namespace std;
int main() {
    int n;
    cin >> n;
    if (n < 9) {
        cout << n << endl;
        return 0;
    }
    unordered_map<string, int> m;
    

    for (int i = 1; i <= n; ++i) {
        string s = to_string(i);
        if (s.back() == '0') continue;
        string t{s.front()}, u{s.back()};
        string x = t + u;
        //cout << x << endl;
        m[x] += 1;
    }
    
    for (auto x : m) {
        string tmp = x.first;
        int a;
        reverse(tmp.begin(), tmp.end());
        if (tmp != x.first) {
            a = m[tmp];
        }
        //cout << x.first << ", " << x.second << ", " << m[tmp] << ", " << ans << endl;
    }
    long long ans = 0;
    for (auto x : m) {
        string tmp = x.first;
        reverse(tmp.begin(), tmp.end());
        if (tmp == x.first) {
            ans += x.second * (x.second - 1) + x.second;
        } else {
          ans += (m[tmp] * x.second);
        }
        //cout << x.first << ", " << x.second << ", " << m[tmp] << ", " << ans << endl;
    }
    cout << ans << endl;
    return 0;
}

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

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


int main()
{
	int n, y; cin >> n >> y;
	y /= 1000;
	vector<int> ans(3, -1);
	rep(i, 0, n)rep(j, 0, n - i)
	{
		if (y - 10 * i - 5 * j == n - i - j)ans = { i,j,n - i - j };
	}
	cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;
}

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

def solve(N: int, S: str):
    sub = 0
    rgb = defaultdict(int)
    for i in range(N):
        rgb[S[i]] += 1
        for j in range(i + 1, N):
            if 2 * j - i >= N:
                break
            if S[i] != S[j] and S[j] != S[2 * j - i] and S[i] != S[2 * j - i]:
                sub += 1

    print(rgb["R"] * rgb["G"] * rgb["B"] - sub)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9480
n = int(input())

ans = [0]*(n+1)
count = 0
for x in range(1, 101):
    count += 1
    if x**2 + 2*x > n:
        break
    for y in range(1, 101):
        if(x**2 + y**2 + x*y + 3) > n:
            break
        for z in range(1, 101):
            num = (x+y+z)**2 - x*y - y*z - z*x
            if num > n:
                break
            ans[num] += 1

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


Measured memory_bytes: 9244
// after YouTube explanation
use proconio::{input, fastout};
use std::cmp;

fn chmax(y: &mut i32, x: i32) {
    if *y < x { *y = x; }
}

fn upd(dp: &mut Vec<Vec<i32>>, n: usize, i: usize, j: usize, x: i32){
    chmax(&mut dp[i][j], x);
    chmax(&mut dp[j][i], x);
    chmax(&mut dp[i][n], x);
    chmax(&mut dp[n][i], x);
    chmax(&mut dp[n][j], x);
    chmax(&mut dp[j][n], x);
    chmax(&mut dp[n][n], x);
}

#[fastout]
fn main() {
    input! {
        n: usize,
        mut a: [usize; n*3],
    }
    for i in 0..a.len() {a[i] -= 1}
    let mut dp: Vec<Vec<i32>> = vec![vec![-1000000000;n+1];n+1];
    upd(&mut dp, n, a[0], a[1], 0);
    let mut base = 0;
    for aa in a[2..].chunks_exact(3) {
        let mut x = aa[0];
        let mut y = aa[1];
        let mut z = aa[2];
        if x==y && y==z {
            base += 1;
            continue;
        }
        let mut q = Vec::new();
        for _ in 0..3 {
            for ai in 0..(n+1) {
                let mut now = dp[ai][n];
                if y==z { now = cmp::max(now,dp[ai][y]+1)}
                q.push((ai,x,now));
            }
            let now = cmp::max(dp[n][n], dp[z][z]+1);
            q.push((x,y,now));
            let t = x; x = y; y = z; z = t;
        }
        for (x,y,now) in q {upd(&mut dp, n, x, y, now)}
    }
    let mut ans = dp[n][n];
    let l = a[n*3-1];
    ans = cmp::max(ans, dp[l][l]+1);
    ans += base;
    println!("{}", ans);
}


Measured memory_bytes: 18120
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))
#define iter(v,ite) for(auto ite=(v).begin();ite!=(v).end();ite++)
#define mimunum(v,x) distance((v).begin(),lower_bound((v).begin(),(v).end(),x))

int n;
int d[100005];
int main(void){
	scanf("%d",&n);
	rep(i,n)scanf("%d",&d[i]);
	int s=0;
	rep(i,n){
		if(i+1==d[d[i]-1])s++;
	}
	printf("%d\n",s/2);
	return 0;
}






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

int main()
{
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    int sum = 0;
    int ma = 10;
    for(int i = 0; i < 5; i++){
        int a;
        cin >> a;
        int mod = a%10;
        if(mod == 0){
            sum += a;
        }else{
            if(mod < ma) ma = mod;
            sum += (a + 10 - mod);
        }
    }
    sum -= 10-ma;
    cout << sum << endl;

}


Measured memory_bytes: 256
S = input()
ans = 'WA'
if S[0] == 'A':
	if S[2:-1].count('C') == 1:
		p = 0
		for i in range(2, len(S)-1):
			if S[i] == 'C':
				p = i
		if S[1:p].islower() and S[p+1:].islower():
			ans = 'AC'
print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<string>
using namespace std;
int main(){
  string t,h;
  int n,pt=0,ph=0;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> t >> h;
    if(t==h)pt++,ph++;
    else if(t>h) pt+=3;
    else ph+=3;
  }
  cout << pt << " " << ph << endl;
}


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

int main(){

  int a,b,c,d;
  cin >> a >> b	>> c >>	d;
  if(a*b>=c*d){
    cout << a*b	<< endl;
  }else{
    cout << c*d	<< endl;
  }


}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val v = (0 until n).map { sc.next().toInt() }
    println(problem111c(n, v))
}

fun problem111c(n: Int, v: List<Int>): Int {
    val grouping = v.groupBy { it }.toList().sortedBy { it.second.count() }
    val mostNum = grouping.last().first
    val nextNum = if (grouping.size == 1) mostNum + 1 else grouping[grouping.size - 2].first
    var count1 = 0
    for (i in 0 until v.size) {
        if ((i + 1) % 2 == 0 && v[i] != mostNum) {
            count1++
        } else if ((i + 1) % 2 != 0 && v[i] != nextNum) {
            count1++
        }
    }
    var count2 = 0
    for (i in 0 until v.size) {
        if ((i + 1) % 2 == 0 && v[i] != nextNum) {
            count2++
        } else if ((i + 1) % 2 != 0 && v[i] != mostNum) {
            count2++
        }
    }

    return Math.min(count1, count2)
}

Measured memory_bytes: 79076
#include <bits/stdc++.h>
#define PI 3.141592653
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
ll gcd(ll x,ll y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
int main(void){
    int n,k;
    cin>>n>>k;
    vector<double> a(n),num(n+1,0);
    rep(i,0,n) {
        int p;
        cin>>p;
        a[i]=p*(p+1)/(2.0*p);
    }
    rep(i,0,k){
        num[0]+=a[i];
    }
    double ans=num[0];
    for(int i=1;i<=n-k+1;i++) {
        double val=0;
        val=num[i-1]+a[i+k-1]-a[i-1];
        num[i]=val;
        ans=max(ans,num[i]);
    }
    printf("%lf\n",ans);
    return 0;
}

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

#define pii pair<int, int>

pii operator-(const pii &obj1, const pii &obj2)
{
  pii tmp;
  tmp.first = obj1.first - obj2.first;
  tmp.second = obj1.second - obj2.second;
  return tmp;
}

int main()
{
  int n;
  while (cin >> n && n) {
    vector<pii> ln;
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        if (i) {
           x -= ln[0].first;
           y -= ln[0].second; 
        }
        ln.push_back(pii(x, y));
    }
    ln[0] = pii(0, 0);
    for (int nc = 1; nc <= n; nc++) {
      cin >> m;
      vector<pii> ln2, ln3;
      for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        ln2.push_back(pii(x, y));
      }
      ln3 = ln2;
      reverse(ln3.begin(), ln3.end());
      for (int i = 1; i < ln3.size(); i++) {
        ln2[i] = ln2[i] - ln2[0];
        ln3[i] = ln3[i] - ln3[0];
      }
      ln2[0] = pii(0, 0);
      ln3[0] = pii(0, 0);
      
      // x = x*cos - y*sin, y = x*sin + y*cos
      // int cs[] = {1, 0, -1, 0};
      // int sn[] = {0, 1, 0, -1};
      for (int i = 0; i < 4; i++) {
        // 90ツ度ツつクツづつ嘉アツ転
        for (int j = 0; j < ln2.size(); j++) {
          ln2[j] = pii(-ln2[j].second, ln2[j].first);
          ln3[j] = pii(-ln3[j].second, ln3[j].first);
          //       printf("(%d, %d)\n", ln2[j].first, ln2[j].second);
        }
        if (ln == ln2 || ln == ln3)
          cout << nc << endl;
      }
    }
    cout << "+++++" << endl;
  } 
}

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

int isIn(int x, int min, int max) {
    return min <= x && x <= max;
}

int getGrade(int rating) {
    if (isIn(rating, 400, 599)) return 8;
    else if (isIn(rating, 600, 799)) return 7;
    else if (isIn(rating, 800, 999)) return 6;
    else if (isIn(rating, 1000, 1199)) return 5;
    else if (isIn(rating, 1200, 1399)) return 4;
    else if (isIn(rating, 1400, 1599)) return 3;
    else if (isIn(rating, 1600, 1799)) return 2;
    else if (isIn(rating, 1800, 1999)) return 1;
    else return 0;
}

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

    cout << getGrade(x) << endl;
    
    return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define N 1005
#define p 1000000007
#define ll long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;

int n,m,a[N][N],st,fa[N],cnt1,cnt2;
ll X,sum;
bool vis[N<<1];
struct node{int u,v,w;bool operator < (const node b) const {return w<b.w;};}e[N<<1];
vector<pii>to[N];

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void dfs(int x,int f)
{
	for(auto e:to[x])
		if(e.first!=f)
		{
			a[st][e.first]=max(a[st][x],e.second);
			dfs(e.first,x);
		}
}

inline int mul(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=(ll)ans*a%p;
		a=(ll)a*a%p;b>>=1;
	}
	return ans;
}

int main()
{
	scanf("%d%d%lld",&n,&m,&X);
	for(int i=1;i<=n;++i) fa[i]=i;
	for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+1+m);
	for(int i=1;i<=m;++i)
	{
		int u=e[i].u,v=e[i].v;
		int t1=find(u),t2=find(v);
		if(t1==t2) continue;
		fa[t1]=t2;
		to[u].push_back(mp(v,e[i].w));
		to[v].push_back(mp(u,e[i].w));
		sum+=e[i].w;
		vis[i]=1;
	}
	if(sum>X) return puts("0"),0;
	for(int i=1;i<=n;++i) st=i,dfs(i,0);
	for(int i=1;i<=m;++i)
		if(!vis[i])
		{
			if(X-sum==e[i].w-a[e[i].u][e[i].v]) cnt1++;
			else if(X-sum<e[i].w-a[e[i].u][e[i].v]) cnt2++;
		}
	if(X==sum) printf("%d",((ll)(mul(2,n-1)-2)*mul(2,m-n+1)+(ll)(mul(2,cnt1)-1)*mul(2,cnt2+1))%p);
	else printf("%d",(ll)(mul(2,cnt1)-1)*mul(2,cnt2+1)%p);
}

Measured memory_bytes: 4352
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <typeinfo>
#define PI 3.14159265359
#define INF 99999999;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(n) rep(i, n)
#define EPS 1e-10
typedef long long ll;
using namespace std;
typedef pair<int, int> P;

double distanceAB(double xa, double ya, double xb, double yb);
void trace(int A[], int N);

/*
class Target
{
public:
	vector <string> draw(int n)
	{

	}
};
*/


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

Node *root, *NIL;

void insert(int k)
{
	Node *y = NIL;
	Node *x = root;
	Node *z;
	
	z = (Node *)malloc(sizeof(Node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;
	
	while (x != NIL)
	{
		y = x;
		if (z->key < x->key)
		{
			x = x->left;
		} else {
			x = x->right;
		}
	}
	
	z->parent = y;
	if (y == NIL)
	{
		root = z;
	} else {
		if (z->key < y->key)
		{
			y->left = z;
		} else {
			y->right = z;
		}
	}
}

Node* find(Node *u, int k)
{
	while (u != NIL && k != u->key)
	{
		if (k < u->key) u = u->left;
		else u = u->right;
	}
	return u;
}

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

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


int main()
{
	int n, i, x;
	string com;
	
	cin >> n;
	REP(n)
	{
		cin >> com;
		if (com[0] == 'f')
		{
			cin >> x;
			Node *t = find(root, x);
			if (t != NIL) cout << "yes" << endl;
			else cout << "no" << endl;
		} else if (com == "insert") {
			cin >> x;
			insert(x);
		} else if (com == "print") {
			inorder(root);
			cout << endl;
			preorder(root);
			cout << endl;
		}
	}
	
	return 0;
}


void trace(int A[], int N)
{
	REP(N)
	{
		if (i > 0) cout << " ";
		cout << A[i];
	}
	cout << endl;
}


double distanceAB(double xa, double ya, double xb, double yb)
{
	return sqrt((xb-xa)*(xb-xa) + (yb-ya)*(yb-ya));
}

Measured memory_bytes: 19980
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

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

	    int N=gi();
	    int C=gi();
	    int K=gi();
	    int[] T= new int[N];
	    Queue<Integer> q=new LinkedList<Integer>();
        for(int i=0; i<N;i++) {
            T[i]=gi();
	    }
	    
        Arrays.parallelSort(T);
        
        long s=0;
        long bc=0;
        for(int i=0; i<N; i++) {
        	if ((q.size()!=0) && ((q.size()==C) || (K<T[i]-q.peek()))) {
        		q.clear();
        		bc++;
        	}
        	q.add(T[i]);
        }
        
        if(q.size()!=0)bc++;

		System.out.println(bc);
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 59032
#include <cstdio>
#include <iostream>

using namespace std;

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

int main() {
	int a, b;
	while (scanf("%d%d", &a, &b) != EOF) {
		printf ("%d\n", gcd(a, b));
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) ll((a).size())
#define out(a) cout<<(a)<<endl;
const ll inf=1e9;
const int MAX = 510000;
const ll MOD = 998244353;

int main(){
  ll h,w;cin>>h>>w;
  vector<string> g(h);
  ll cnt=0;
  rep(i,0,h){
    cin>>g[i];
    rep(j,0,w){
      if(g[i][j]=='#'){cnt++;}
    }
  }
  if(cnt==h+w-1){
    cout<<"Possible"<<endl;
  }
  else cout<<"Impossible"<<endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
const int mod=1000000007;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m;cin >> n >> m;
	vector<pii> a(m);
	rep(i,m) cin >> a.at(i).second >> a.at(i).first;
	sort(a.begin(),a.end());
	int ans=0,r=0;
	rep(i,m){
		if(a.at(i).second>=r){
			r=a.at(i).first;
			ans++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<53;
ll Sum[100];
ll n,m,a,b,p,q;


ll calc(ll k){
  ll A = 1,B = 1;
  ll res=p+q;
  while(0<res&&res<=INF&&k--)A*=a,B*=b,res=p*A+q*B;
  if(res<0||res>INF)res=INF;
  return res;
}


ll ans = INF;
set<ll> used[101];
void dfs(ll pos,ll sum){
  ans = min(ans,(ll)abs(m-sum));
  if(m<sum||pos==-1||sum<0LL||sum>INF) return;
  if(Sum[pos]+sum<m){ans=min(ans,m-(Sum[pos]+sum));return;}
  if(used[pos].count(sum)) return ;
  used[pos].insert(sum);
  dfs(pos-1,sum+calc(pos));  
  dfs(pos-1,sum);
}


int main(){
  cin>>n>>m>>a>>b>>p>>q;
  for(int i=0;i<60;i++) Sum[i] = INF;
  Sum[0] = calc(0);
  for(int i=1;i<60;i++)Sum[i]=min(INF,calc(i)+Sum[i-1]);

  if(max(a,b)==1) {
    ll s = abs(m - (m/(p+q))*(p+q));
    ll t = abs(m - (m/(p+q))*(p+q) - (p+q));
    if(m/(p+q)==n) t = INF;
    if(m/(p+q)<=n) cout<<min(s,t)<<endl;
    else cout<< m-(p+q)*n <<endl;
    return 0;
  }
  
  dfs(min(n-1,50LL),0);
  cout<<ans<<endl;
  return 0;
}

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

using namespace std;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

typedef long long  ll;
#define endl '\n'


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


const int MOD = 1000000007;

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

int n;

void Input() {

    cin >> n;
}

void Solve() {

    for(int i = 1; i < 10; i++) {

        if(n / i < 10) {

            cout << "Yes" << endl;

        }
    }
}

int main() {

  cin.tie(0);
  ios::sync_with_stdio(false);
  Input();
  //Solve();

    for(int i = 1; i < 10; i++) {

        if(n % i  == 0) {

            if(n / i < 10) {
            //cout << i << " " << n / i << endl;
            cout << "Yes" << endl;
            return 0;
            }
        }

    }

    cout << "No" << endl;
  return 0;

}



Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    h, a = LI()
    print((h - 1) // a + 1)
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 38640
#include<bits/stdc++.h>
using namespace std;
int n,k,ans; 
int main()
{
	cin>>n>>k;
	ans=1;
	for(int i=0;i<n;i++)
    {
    	ans+=min(ans,k); 
    }
    cout<<ans<<endl;


	return 0;
}


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

typedef long long ll;

ll cnt_m;
ll cnt_b;

//分割統治で考える。Aはもともとswapされる配列なので、mergeSortで分割した後、R[]の項が選ばれれば
//swap回数が減る。

ll merge(int A[],int left,int mid,int right)
{
  ll res = 0;
  
  int n1 = mid - left;
  int n2 = right - mid;

  int L[n1+1],R[n2+1];
  for(int i=0;i < n1;i++){
    L[i] = A[left+i];
  }
  for(int i=0;i < n2;i++){
    R[i] = A[mid+i];
  }
  
  L[n1]=R[n2]=INF;
  
  int i=0,j=0;
  for(int k=left;k < right;k++){
    if(L[i] <= R[j]){
      A[k] = L[i++];
    }
    else{
      A[k] = R[j++];
      res += n1-i;
      //R[]の項が選ばれたとき、swapの回数が減る。(iが増える)
      //また、
    }
  }
  return res;
}

ll mergeSort(int A[],int left,int right)
{
  ll cnt1,cnt2,cnt3;
  
  if(left+1 < right){
    int mid = (left + right)/2;
    cnt1 = mergeSort(A,left,mid);
    cnt2 = mergeSort(A,mid,right);
    cnt3 = merge(A,left,mid,right);
    return cnt1+cnt2+cnt3;
  }
  else return 0;
}

int bubbleSort(int A[],int n)
{
  int i,j;
  int temp;
  
  for(i = 0; i < n ;i++){
    for(j = n-1; j > i ;j--){
      
      if( A[j-1] > A[j] ){
	swap(A[j-1],A[j]);
	cnt_b++;
      }
    }
  }
}

int main()
{
  int i;
  int n;
  int A[200001];
  int B[200001];
  
  scanf("%d",&n);

  for(i = 0;i < n;i++){
    scanf("%d",&A[i]);
    B[i] = A[i];
  }

  cnt_m = mergeSort(A,0,n);

  //bubbleSort(B,n);

  //for(int i=0;i < n;i++) cout << A[i];
  //cout << endl;

  //cout << cnt_m << endl << "cnt_b = " << cnt_b << endl;
  cout << cnt_m << endl;
  return 0;
}



Measured memory_bytes: 4812
import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    private static StringTokenizer st;

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

    public static void main(String[] args) throws IOException {
        int N = readInt();
        int M = readInt();
        int K = readInt();
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = readInt();
        }
        int[] b = new int[M];
        for (int i = 0; i < M; i++) {
            b[i] = readInt();
        }

        int minutesLeft = K;
        int aIndex = -1;
        while (aIndex + 1 < N && a[aIndex + 1] <= minutesLeft) {
            aIndex++;
            minutesLeft -= a[aIndex];
        }
        int maxBooks = aIndex + 1;

        int bIndex = -1;
        while (minutesLeft >= 0) {
            while (bIndex + 1 < M && b[bIndex + 1] <= minutesLeft) {
                bIndex++;
                minutesLeft -= b[bIndex];
            }

            int current = aIndex + bIndex + 2;
            if (maxBooks < current) maxBooks = current;

            if (aIndex >= 0) {
                minutesLeft += a[aIndex];
                aIndex--;
            } else break;
        }

        pw.println(maxBooks);
        pw.close();
    }
}


Measured memory_bytes: 59844
INF = 10 ** 100


def solve(ns):
    n = len(ns)
    ns.sort(reverse=True)
    pos = ns[:(n + 1) / 2]
    neg = ns[(n + 1) / 2:]

    while len(pos) > 1 and pos[-1] < 0:
        neg.append(pos.pop())

    neg.sort()
    while len(neg) > 1 and neg[-1] > 0:
        pos.append(neg.pop())

    ans = sum(pos) - sum(neg)
    print ans

    #print pos, neg

    res = INF
    while pos and neg:
        if len(pos) >= 2 and len(neg) >= 2:
            a1, a2 = pos.pop(), pos.pop()
            b1, b2 = neg.pop(), neg.pop()

            c1 = a1 - b1
            print a1, b1

            c2 = b2 - a2
            print b2, a2

            pos.append(c1)
            neg.append(c2)
        elif len(pos) == 1 and len(neg) == 1:
            a1 = pos.pop()
            b1 = neg.pop()
            c = a1 - b1
            print a1, b1

            res = c
        elif len(neg) == 1:
            assert pos
            a1 = pos.pop()
            b1 = neg.pop()

            c = b1 - a1
            print b1, a1

            if not pos and not neg:
                res = c
            else:
                neg.append(c)
        elif len(pos) == 1:
            assert neg
            a1 = pos.pop()
            b1 = neg.pop()

            c = a1 - b1
            print a1, b1

            if not pos and not neg:
                res = c
            else:
                pos.append(c)
        else:
            print pos, neg
            assert False
    assert res == ans
    assert not pos
    assert not neg
    return res

#assert solve([1, -1]) == 2
#assert solve([1, -1, -5]) == 7
#assert solve([1, -1, 3, 4]) == 9

n = int(raw_input())
ns = map(int, raw_input().split())
solve(ns)



Measured memory_bytes: 11348
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <sstream>
using namespace std;

int main() {
	int n;
	while (cin >> n, n) {
		cin.ignore();
		map<string,int> cnt;
		string s, word;
		for (int i=0; i<n; ++i) {
			getline(cin, s);
			stringstream ss(s);
			while (ss >> word) {
				++ cnt[word];
			}
		}
		char c;
		cin >> c;
		vector<pair<int,string> > v;
		for (auto it : cnt) {
			if (it.first[0] == c) {
				v.push_back(make_pair(-it.second, it.first));
			}
		}
		sort(v.begin(), v.end());
		if (v.empty()) {
			cout << "NA" << endl;
		} else {
			for (int i=0; i<5 && i<(int)v.size(); ++i) {
				cout << (i==0 ? "" : " ") << v[i].second;
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1240
using System.Linq;
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var dp = Enumerable.Repeat(-1, 45).ToArray();
        var ans = Fib(n, dp);
        Console.WriteLine(ans);
    }
   public static int  Fib (int n,int[] dp)
    {
        if (dp[n] != -1) return dp[n];
        if (n == 0 | n == 1) return 1;
        else
        {
            var t1 = Fib(n -1,dp);
            if (dp[n - 1] == -1) dp[n - 1] = t1;
            var t2 = Fib(n - 2, dp);
            if (dp[n - 2] == -1) dp[n - 2] = t2;
            return t1 + t2;
        }
    }
}

Measured memory_bytes: 9452
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
int n,x,pos[110000];
int gcd(int a,int b){
  return (b==0)?a:gcd(b,a%b);
}
signed main(){
  scanf("%lld %lld",&n,&x);
  for(int i=1;i<=n;i++)
    scanf("%lld",&pos[i]);
  for(int i=1;i<=n;i++)
    pos[i]-=x;
  ++n;
  pos[n]=0;
  sort(pos+1,pos+n+1);
  int ans=pos[2]-pos[1];
  for(int i=2;i<=n-1;i++){
    ans=gcd(ans,pos[i+1]-pos[i]);
  }
  printf("%lld",ans);
  return 0;
}


Measured memory_bytes: 896
use std::io::Read;
use std::str::SplitWhitespace;
use std::str::FromStr;

pub fn read_stdin() -> String {
    let mut s = String::new();
    ::std::io::stdin().read_to_string(&mut s).unwrap();
    s
}

pub trait Parse<T> {
    fn parse(&mut self) -> T;
}

impl<'a, T> Parse<T> for SplitWhitespace<'a>
where
    T: FromStr,
{
    fn parse(&mut self) -> T {
        let word = self.next().unwrap();
        word.parse().ok().unwrap()
    }
}

fn main() {
    let source = read_stdin();
    let mut iter = source.split_whitespace();
    let n: usize = iter.parse();
    let ys: Vec<i64> = (0..n).map(|_| iter.parse()).collect();
    let mut x0 = 0;
    let mut sign = 1;
    for &y in &ys {
        x0 += y * sign;
        sign *= -1;
    }

    let mut xs = Vec::new();
    xs.push(x0);

    let mut x = x0;
    for y in ys[..(ys.len() - 1)].into_iter() {
        x = 2 * y - x;
        xs.push(x);
    }

    println!(
        "{}",
        xs.into_iter()
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join(" ")
    );
}

Measured memory_bytes: 15612
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

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

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
  size_t N;
  scanf("%zu", &N);

  std::vector<int> t(N);
  int tsum = 0;
  for (auto& ti: t) {
    scanf("%d", &ti);
    ti += ti;
    tsum += ti;
  }

  std::vector<int> v(N);
  for (auto& vi: v) {
    scanf("%d", &vi);
    vi += vi;
  }

  std::vector<int> maxv{0};
  for (size_t i = 0; i < N; ++i) {
    if (maxv.back() > v[i]) maxv.back() = v[i];
    for (int j = 0; j < t[i]; ++j)
      maxv.push_back(v[i]);
  }
  maxv[tsum] = 0;

  std::vector<int> res(tsum+1);
  for (int i = 0; i <= tsum; ++i) {
    res[i] = 1e9;
    for (int j = 0; j < i; ++j) res[i] = std::min(res[i], res[j]+i-j);
    for (int j = i; j <= tsum; ++j) res[i] = std::min(res[i], maxv[j]+(j-i));
  }

  printf("%.12f\n", std::accumulate(res.begin(), res.end(), 0)/4.0);
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
//#define int long long

using namespace std;
using LL = long long;
using P = pair<int, int>;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

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

const int INF = (int)1e9;
const LL INFL = (LL)1e18;
const int MOD = (int)1e9 + 7;

template <typename T>
class UnionFind {
    private:
        vector<int> parent;  // 親
        vector<int> rank;    // 木の深さ

        // 重み付きUnionFindでのみ利用
        vector<T> diffWeight; // 親ノードとの値の差
    public:
        UnionFind(int n);          // n要素で初期化
        int Find(int x);           // 木の根を返す
        void Unite(int x, int y);  // xとyの属する集合を併合
        bool Same(int x, int y);   // xとyが同じ集合に属するか否か

        // 重み付きUnionFindでのみ利用
        void Unite(int x, int y, T w);
        T Weight(int x);      // xの重みを返す
        T Diff(int x, int y); // xとyの差を返す
};

template <typename T>
UnionFind<T>::UnionFind(int n) : parent(n), rank(n), diffWeight(n, 0){
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

template <typename T>
int UnionFind<T>::Find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        int r = Find(parent[x]);
        diffWeight[x] += diffWeight[parent[x]];
        return parent[x] = r;
    }
}

template <typename T>
void UnionFind<T>::Unite(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;

    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}

template <typename T>
bool UnionFind<T>::Same(int x, int y) { return Find(x) == Find(y); }

template <typename T>
void UnionFind<T>::Unite(int x, int y, T w){
    w += Weight(x); w -= Weight(y);
    x = Find(x); y = Find(y);
    if(x == y) return;

    if(rank[x] < rank[y]) swap(x, y), w = -w;

    if(rank[x] == rank[y]) rank[x]++;
    parent[y] = x;

    diffWeight[y] = w;
}

template <typename T>
T UnionFind<T>::Weight(int x){
    Find(x);
    return diffWeight[x];
}

template <typename T>
T UnionFind<T>::Diff(int x, int y){
    return Weight(y) - Weight(x);
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    UnionFind<int> uf(n);
    bool ans = true;
    REP(i, m){
        int l, r, d;
        cin >> l >> r >> d;
        l--, r--;
        if(!uf.Same(l, r)){
            uf.Unite(l, r, d);
        }else{
            ans &= uf.Diff(l, r) == d;
        }
    }
    cout << (ans ? "Yes" : "No") << endl;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define fi first
#define se second
#define INF 1000000009
#define LLINF 1000000000000000009LL
using ll = long long;

int main(){
  int n,k;
  cin>>n>>k;
  vector<int>a(n);
  rep(i,n)cin>>a[i];
  sort(a.begin(),a.end());
  int ans=0;
  rep(i,k)ans+=a[i];
  cout<<ans<<endl;
  return(0);
}

Measured memory_bytes: 3628
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H, W = MI()
    N = I()
    A = [(int(a),i) for i,a in enumerate(input().split(), start=1)]
    A.sort()

    stack = []
    for a,i in A:
        stack.extend([i] * a)

    ans = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            c = stack.pop()
            if i % 2 == 0:
                ans[i][j] = c
            else:
                ans[i][W - 1 - j] = c
    for a in ans:
        print(*a)


    
if __name__ == '__main__':
    main()

Measured memory_bytes: 42352
#include<bits/stdc++.h>
        #define ll long long
        #define rep(i,a,b) for(i=a;i<b;i++)
        #define pb push_back
        #define all(v) v.begin(),v.end()
        #define F first
        #define S second
        #define vi vector < int >
        #define vii vector < long long int>
        #define CLR(a) memset((a),0,sizeof(a))
        #define mp make_pair
        #define hell 1000000007

        using namespace std;


        void solve()
        {
           ll int i,j=0,r=200,p,q,k=0,d,y=0,h,flag=0,n,m=0,W;
            cin>>n;
            bool v[n+1],vis[2*n+1];
            memset(vis,false,sizeof(vis));
            vector < ll >as;
            rep(i,1,n+1) cin>>v[i];


             for(i=n;i>0;i--)
             {
                y=0;
                 for(j=2*i;j<=n;j+=i)
                 {
                     if(vis[j]) y++;
                 }
                 if(v[i]) y++;
                 if(y%2==v[i] and v[i]){if(v[i]) {as.pb(i); vis[i]=true;}}
                 else if(y%2 and v[i]==0) {as.pb(i); vis[i]=true;}
             }

              cout<<as.size()<<endl;
              rep(i,0,as.size()) cout<<as[i]<<" ";


        }


        int main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0);
            cout.tie(0);
            int t=1;
            //cin>>t;
            while(t--)
            solve();
        }

           /*

      void bfs( int i , int j)
           {
               vis[i][j]= true;
             queue < int > que;
             que.push(k);
             while(!que.empty())
             {
                int x= que.front();
                que.pop();
                 for ( int i=1;i<=n;i++)
                 {
                     if((!g[1][n] and g[x][i] ) or (g[1][n] and ! g[x][i]))
                     {
                       if(!vis[i])
                       {
                           que.push(i);
                           level[i]=level[x]+1;
                           vis[i]= true;
                       }
                     }
                 }
             }
           }

          ll int por(ll int a,ll int b)
             {
                ll int k=1;
                while(b>0)
                {
                    if(b%2) k=k*a,k%=hell;
                    b/=2;
                    a*=a; a%=hell;
                }
                return k;
             } */


Measured memory_bytes: 2804
mod = 10 ** 9+7


def inv(x):
    return pow(x, mod - 2, mod)


r1, c1, r2, c2 = map(int, input().split())
fact, inv_fact = [1, 1], [1, 1]
for i in range(2, r2+c2+3):
    fact.append(fact[-1] * i % mod)
    inv_fact.append(inv(fact[-1]))


def nCr(n, r):
    return fact[n] * inv_fact[r] * inv_fact[n-r] % mod


def path_sum_sum(r, c):
    return ((r + 2) * nCr(c+r+2, r+2) % mod + mod - c - 1) * inv(c + 1) % mod


ans = (path_sum_sum(r2, c2) + mod - path_sum_sum(r2, c1-1) +
       mod - path_sum_sum(r1-1, c2) + path_sum_sum(r1-1, c1-1))
print(ans % mod)


Measured memory_bytes: 136824
import numpy as np
from math import factorial

# combination の実装は以下参照
# https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E7%95%AA%E5%A4%96%E7%B7%A8

from operator import mul
from functools import reduce

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


x, y = [int(i) for i in input().split()]

points = np.array([[1, 2], [2, 1]])
values = np.array([x, y])
a, b = np.linalg.solve(points, values).tolist()

if a.is_integer() and b.is_integer():
  a = int(a)
  b = int(b)

  r = a if a < b else b

  print(cmb(a+b, r, 10 ** 9 + 7))

else:
    print(0)


Measured memory_bytes: 133700