akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
//#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
int main(){
    string s;cin>>s;
    int ans=0;
    string t="CODEFESTIVAL2016";
    rep(i,s.size())if(s[i]!=t[i])ans++;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll N,ans=0; cin>>N;
  vector<ll> used(1000010,0);
  vector<ll> Z(N,0);
  for(ll i=0; i<N; i++){
    ll A; cin>>A;
    Z[i]=A;
    used[A]++;
  }
  for(ll i=0; i<N; i++){
    //約数
    ll n=Z[i];
    vector<ll> B(0,0);
    for(ll j=1; j*j<=n; j++){
      if(n%j==0){
        B.emplace_back(j);
        if(n/j==j) continue;
        B.emplace_back(n/j);
      }
    }
    ll bsz=B.size();
    for(ll j=0; j<bsz; j++){
      if(B[j]<n && used[B[j]]>0) break;
      if(B[j]==n && used[B[j]]>1) break;
      if(j==bsz-1) ans++;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 12712
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int N, K, ans = 0, nextint;
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &nextint);
		if (nextint >= K) ++ans;
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 128
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>

using namespace std;

typedef long long ll;

mt19937 rnd(228);

int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector <int> cnt(n);
    vector <bool> red(n);
    for (int i = 0; i < n; i++)
    {
        cnt[i] = 1;
    }
    red[0] = true;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        x--, y--;
        cnt[x]--, cnt[y]++;
        if (red[x]) red[y] = true;
        if (!cnt[x]) red[x] = 0;
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (red[i])
        {
            ans++;
        }
    }
    cout << ans << '\n';
}


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

int main(int argc, char** argv){
  // 受け取り
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  
  // a[i]: 0~i番目までにACがいくつ含まれるか
  int a[N];
  int numAC = 0;
  int idx = 0;
  for(idx=0; idx < N-1; idx++){
    a[idx] = numAC;
    if(S[idx] == 'A' && S[idx+1] == 'C'){
      numAC++;
      idx++;
      a[idx] = numAC;
    }
  }
  a[idx] = numAC;
  
/*
  for(int cnt1=0; cnt1 <= N-1; cnt1++){
    cout << "cnt: " << cnt1 << ", a[" << cnt1 << "]: " << a[cnt1] << endl;
  }
*/
  
  // l, rを逐次受け取る

  for(int cnt0=0; cnt0<Q; cnt0++) {
    int l, r;
    cin >> l >> r;
    l--; r--;
    printf("%d\n", a[r]-a[l]);
  }
  return 0;  
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
int n, mn;
map<string, int> m;
map<string, int>::iterator it;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        m[str]++;
        mn = max(mn, m[str]);
    }
    for (it = m.begin(); it != m.end(); it++)
    {
        if ((*it).second == mn)
        {
            cout << (*it).first << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 23808
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, ans; ll d, x, y;

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cin >> n >> d, d *= d; 
    while (n--)
        if (cin >> x >> y, x*x+y*y <= d)
            ++ans;
    cout << ans; }


Measured memory_bytes: 3636
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <sstream>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <unordered_map>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}

template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";}
template <typename T, typename... V>void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef HOME
#warning CHECK int:ll::INT_MAX:LLONG_MAX
#define maxn 20
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define maxn 2000006
#define gcd __gcd
#define debug(x...)
#endif

#define ff first
#define endl '\n'
#define ss second
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define PI 3.14159265358979323846264338327950L
#define f(i,x,n) for(int i=x;i<=n;i++)
#define fr(i,x,n) for(int i=x;i>=n;i--)
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

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


int main() {

	int n; cin >> n;
	cout << (n / 2) + (n % 2);

	return 0;
}

Measured memory_bytes: 3152
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);		
		String s = sc.next();
        if(s.substring(5,7).equals("01")||s.substring(5,7).equals("02")||
           s.substring(5,7).equals("03")||s.substring(5,7).equals("04")){
          System.out.println("Heisei");}
      else{System.out.println("TBD");}		
	}
}

Measured memory_bytes: 23508
s = input()
q = int(input())
lead = ''
end = ''
inversion_flg = -1

for j in range(q):
    query = input().split()
    if query[0] == "1":
        inversion_flg *= -1
    else:
        if inversion_flg == 1:
            if query[1] == "1":
                query[1] = "2"
            else:
                query[1] = "1"
        if query[1] == "1":
            lead += query[2]
        else:
            end += query[2]

lead = lead[::-1]
s = lead + s + end
if inversion_flg == 1:
    s = s[::-1]
print(s)


Measured memory_bytes: 4388
#include <bits/stdc++.h>
using namespace std;
using namespace std;
 
#define ll long long
#define f(i,a,b) for(int i=a;i<b;i++)
#define endl '\n'
#define spc " "
#define pb push_back
#define mp make_pair


int main() 

{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll n;
    cin>>n;
    ll a[n];
    f(i,0,n-1){
        cin>>a[i];
    }
    map<ll,ll>m;
    f(i,1,n+1) m[i]=0;
    f(i,0,n-1){
        m[a[i]]++;
    }
    f(i,1,n+1){
        cout<<m[i]<<endl;
    }


}

Measured memory_bytes: 17744
#include <iostream>
#include <algorithm>
#include <vector>
 
void solve() {
    int n;
    std::cin >> n;
 
    std::vector<int> xs(n), ys(n);
    for (auto& x : xs) std::cin >> x;
    for (auto& y : ys) std::cin >> y;
 
    std::vector<int> xr(n + 1, -1), yl(n + 1, -1);
    for (int i = 0; i < n; ++i) xr[xs[i]] = i;
    for (int i = n - 1; i >= 0; --i) yl[ys[i]] = i;
 
    int d = 0;
    for (int i = 1; i <= n; ++i) {
        if (xr[i] == -1 || yl[i] == -1) continue;
        d = std::max(d, xr[i] - yl[i] + 1);
    }
 
    std::rotate(ys.begin(), ys.begin() + n - d, ys.end());
 
    for (int i = 0; i < n; ++i) {
        if (xs[i] == ys[i]) {
            std::cout << "No\n";
            return;
        }
    }
 
    std::cout << "Yes\n";
    for (auto y : ys) std::cout << y << " ";
    std::cout << "\n";
}
 
int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
 
    solve();
 
    return 0;
}

Measured memory_bytes: 6368
#include <stdio.h>
int main()
{
    int n,a[100000],s=0,i;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        s=s+a[i];
    }
    s=s-n;
    printf("%d\n",s);
    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

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

  long long cnt[] = {0, 0, 0, 0, 0};
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    if (s[0] == 'M') {
      cnt[0]++;
    }
    if (s[0] == 'A') {
      cnt[1]++;
    }
    if (s[0] == 'R') {
      cnt[2]++;
    }
    if (s[0] == 'C') {
      cnt[3]++;
    }
    if (s[0] == 'H') {
      cnt[4]++;
    }
  }

  int a[] = {0, 0, 1, 1, 1};
  long long ans = 0;
  do {
    long long t = 1;
    for (int i = 0; i < 5; i++) {
      if (a[i]) {
        t *= cnt[i];
      }
    }
    ans += t;
  } while (next_permutation(a, a + 5));

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

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

template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
  int d, n;
  cin >> d >> n;
  vector<int> t(d);
  rep(i,d) cin >> t[i];
  vector<int> a(n), b(n), c(n);
  rep(i,n) cin >> a[i] >> b[i] >> c[i];
  vector<vector<int>> dp(d,vector<int>(n,-1));
  rep(i,n){
    if(a[i]<=t[0] && b[i]>=t[0])
      dp[0][i] = 0;
  }
  for(int i=1; i<d; i++){
    rep(j,n){
      if(a[j]<=t[i] && b[j]>=t[i]){
        rep(k,n){
          if(dp[i-1][k]!=-1)
            chmax(dp[i][j], dp[i-1][k]+abs(c[k]-c[j]));
        }
      }
    }
  }
  int ans=0;
  rep(i,n) ans = max(ans, dp[d-1][i]);
  cout << ans << endl;
  return 0;
}


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define endl "\n"

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

  int N,x;
  cin>>N>>x;
  vector<int>a(N);
  for(int i=0;i<N;i++)cin>>a[i];
  ll ans=0;
  for(int i=0;i<N;i++)if(a[i]>x){
    ans+=a[i]-x;
    a[i]=x;
  }
  for(int i=0;i<N-1;i++){
    if(a[i]+a[i+1]>x){
      int d=a[i+1]+a[i]-x;
      if(d<=0)continue;
      if(d>a[i+1])ans+=a[i+1],a[i+1]=0;
      else ans+=d,a[i+1]-=d;
    }
  }
  for(int i=N-1;i>=1;i--){
    if(a[i]+a[i-1]>x){
      int d=a[i]+a[i-1]-x;
      if(d<=0)continue;
      if(d>a[i-1])ans+=a[i-1],a[i-1]=0;
      else ans+=d,a[i-1]-=d;
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

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

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

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

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

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

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

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

#[allow(unused_imports)]
use std::io::{stdin, stdout, Read, Write, BufWriter};
#[allow(unused_imports)]
use std::cmp::{max, min};

fn main() {
    let table = dirty_table_formatter();
    let m = table[0][1];
    let mut ans: i32 = 0;
    for i in 1..(m+1) {
        if table.iter().skip(1).all(|v| v[1..].contains(&i)) { ans += 1; }
    }
    println!("{}", ans);
}

type SomeInt = i32;
fn dirty_table_formatter() -> Vec<Vec<SomeInt>> {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    s.trim().lines()
        .map(|line| line.trim().split_whitespace()
             .map(|x| x.parse::<SomeInt>().unwrap())
             .collect::<Vec<SomeInt>>())
        .collect()
}


Measured memory_bytes: 4352
N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
cnt=0
t=[[0]for i in range(K)]
for i in range(N):
    if T[i]=="r":
        if t[i%K]!="p":
            cnt+=P
            t[i%K]="p"
        else:
            t[i%K]="0"
    if T[i]=="p":
        if t[i%K]!="s":
            cnt+=S
            t[i%K]="s"
        else:
            t[i%K]="0"
    if T[i]=="s":
        if t[i%K]!="r":
            cnt+=R
            t[i%K]="r"
        else:
            t[i%K]="0"
    

print(cnt)


Measured memory_bytes: 51440
N, M = map(int, input().split())
ac = 0
pena = 0
count = [0 for _ in range(N+1)]
for _ in range(M):
  p, S = input().split()
  p = int(p)
  if S == 'AC':
    if count[p] > -1:
      pena += count[p]
      ac += 1
    count[p] = -10**5-1
  else:
    count[p] += 1
  
print(ac, pena)
  


Measured memory_bytes: 9904
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int main()
{
    int rect_w, rect_h, x, y, r;
    cin >> rect_w >> rect_h >> x >> y >> r;

    if (0 <= x - r && x + r <= rect_w && 0 <= y - r && y + r <= rect_h) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

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

double px[20],py[20];

double flon(int a,int b,int c){
  double len1,len2,len3;
  double s;

  len1 = sqrt( (px[a]-px[b])*(px[a]-px[b]) + (py[a]-py[b])*(py[a]-py[b]) );
  len2 = sqrt( (px[b]-px[c])*(px[b]-px[c]) + (py[b]-py[c])*(py[b]-py[c]) );
  len3 = sqrt( (px[a]-px[c])*(px[a]-px[c]) + (py[a]-py[c])*(py[a]-py[c]) );

  s = (len1 + len2 + len3) / 2.0;

  return sqrt( s * (s-len1) * (s-len2) * (s-len3) );
}

int main(void){
  int i;
  int n;
  double sum;

  n = 0;
  while(scanf("%lf,%lf ",&px[n],&py[n])!=EOF)n++;

  sum = 0.0;
  for(i=1;i<n-1;i++){
    sum += flon(0,i,i+1);
  }

  printf("%lf\n",sum);

  return 0;
}

Measured memory_bytes: 0
from itertools import permutations
N,M,R=map(int,input().split())
INF=10**9
d=[[INF]*N for i in range(N)]
r=list(map(int,input().split()))
for i in range(M):
  A,B,C=map(int,input().split())
  d[A-1][B-1]=C
  d[B-1][A-1]=C
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=10**9
for L in permutations(r):
  temp=0
  for j in range(R-1):
    temp+=d[L[j]-1][L[j+1]-1]
  ans=min(temp,ans)
print(ans)


Measured memory_bytes: 47960
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, n) for (int i = (n-1); i >= 0; i--)
#define rea(i, a, b) for (int i = (a); i < (b); i++)
#define reab(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(),(a).end()
#define SZ(x) ((int)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;
/* END OF TEMPLATE */

int bit(int n, int s){
    return (n >> s) % 2;
}

int lastzero(int n, int D){
    int c = D;
    rep(i, D){
        if(n % 2 == 0) c = i;
        n >>= 1;
    }
    return c;
}

int main(){
    ll D, G;
    cin >> D >> G;
    G /= 100;
    vll p(D), c(D);
    rep(i, D){
        cin >> p[i] >> c[i];
        c[i] /= 100;
    }
    vll req(1 << D, 0);
    vll ans(1010, 0);
    rep(i, 1 << D){
        ll comp = 0;
        rep(j, D){
            req[i] += p[j] * bit(i, j);
            comp += ((j+1) * p[j] + c[j]) * bit(i, j);
        }
        ans[req[i]] = max(ans[req[i]], comp);
        ll rest = lastzero(i, D);
        if(rest >= 0 && rest < D){
            rep(j, p[rest]){
                ans[req[i]+j] = max(ans[req[i]+j], comp + (rest+1) * j);
            }
        }
    }
    auto itr = lower_bound(ans.begin(), ans.begin() + req[(1 << D)-1], G);
    cout << distance(ans.begin(), itr) << endl;
}

Measured memory_bytes: 256
import heapq
from operator import itemgetter

n, k = map(int, input().split())
sushi = [tuple(map(int, input().split())) for _ in range(n)]

sushi.sort(key=itemgetter(1), reverse=True)
que = []
kind = set()
res = 0
for t, d in sushi[:k]:
    if t in kind:
        heapq.heappush(que, d)
    else:
        kind.add(t)
    res += d
res += len(kind)**2

val = res
for t, d in sushi[k:]:
    if not que:
        break
    if t in kind:
        continue
    val += -heapq.heappop(que) + d + len(kind)*2 + 1
    kind.add(t)
    res = max(res, val)

print(res)


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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (300006)
ll n, dp[MAXN][2], sz[MAXN]; // dp(i, 0) = low, dp(i, 1) = high, observation is that high and low have the same parity
bool A[MAXN];
vector<int> v[MAXN];
int low=0, high=1;
void dfs(int x,int p) {
	sz[x] = A[x];
	for(auto i:v[x]) if(i^p) dfs(i, x), sz[x]+=sz[i];
	// dp(x,0) = max(summation{dp(i,0)}&1, max{dp(i)[low,high,2]}*2 - summation{dp(i)[low,high,2]})
	pi mx = pi(-LLINF, -LLINF);
	for(auto i:v[x]) if(i^p) {
		dp[x][high] += dp[i][high] + sz[i];
		mx = max(mx, pi(dp[i][high]+sz[i], dp[i][low]+sz[i]));
	}
	if(mx.s > dp[x][high] - mx.f) {
		dp[x][low]=mx.s-(dp[x][high]-mx.f);
	} else {
		dp[x][low]=dp[x][high]&1;
	}
}
int main()
{
	cin>>n;
	FOR(i,1,n) { char ch; cin>>ch; if(ch=='1') A[i]=1; }
	FOR(i,1,n-1) {
		ll a,b;cin>>a>>b;
		v[a].eb(b),v[b].eb(a);
	}
	ll ans = LLINF;
	FOR(r,1,n) {
		mmst(dp,0), mmst(sz,0);
		dfs(r, r);
		if(dp[r][low]==0) ans=min(ans, dp[r][high]>>1);
	}
	if(ans==LLINF) ans=-1;
	cout<<ans<<'\n';
}


Measured memory_bytes: 14848
#include <stdio.h>

typedef struct {
    int t;
    int x;
    int y;
} POINT;

int main(void)
{
    int n;
    POINT p[100001] = { 0, 0, 0 };
    int flag = 1;
    int i, sx, sy, s, t;

    scanf("%d", &n);
    for (i=1; i<=n; i++) {
        scanf("%d%d%d", &p[i].t, &p[i].x, &p[i].y);
    }


    for (i=1; i<=n; i++) {
        sx = p[i].x - p[i-1].x;
        if (sx<0) sx=-sx;
        sy = p[i].y - p[i-1].y;
        if (sy<0) sy=-sy;
        s = sx + sy;
        t = p[i].t - p[i-1].t;

        if (!(s<=t && (t-s)%2==0)) {
            flag = 0;
            break;
        }
    }

    if (flag)   printf("Yes\n");
    else        printf("No\n");

    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
int main(void){
    std::map<double, int> map4;
    int p;
    double t;
    std::map<double, int> map1;
    for (int i=0;i<8;i++) {
        cin>>p>>t;
        map1.insert(make_pair(t,p));
    }
    auto itr1=map1.begin();
    printf("%d",itr1->second);
    cout<<" ";
    printf("%.2f",itr1->first);
    cout<<endl;
    itr1=next(itr1,1);
    printf("%d",itr1->second);
    cout<<" ";
    printf("%.2f",itr1->first);
    cout<<endl;
    
    
    std::map<double, int> map2;
    for (int j=0;j<8;j++) {
        cin>>p>>t;
        map2.insert(make_pair(t,p));
    }
    auto itr2=map2.begin();
    printf("%d",itr2->second);
    cout<<" ";
    printf("%.2f",itr2->first);
    cout<<endl;
    itr2=next(itr2,1);
    printf("%d",itr2->second);
    cout<<" ";
    printf("%.2f",itr2->first);
    cout<<endl;
    
    
    std::map<double, int> map3;
    for (int j=0;j<8;j++) {
        cin>>p>>t;
        map3.insert(make_pair(t,p));
    }
    auto itr3=map3.begin();
    printf("%d",itr3->second);
    cout<<" ";
    printf("%.2f",itr3->first);
    cout<<endl;
    itr3=next(itr3,1);
    printf("%d",itr3->second);
    cout<<" ";
    printf("%.2f",itr3->first);
    cout<<endl;
    
    for (int k=0;k<6;k++) {
        itr1=next(itr1,1);
        map4.insert(make_pair(itr1->first,itr1->second));
        itr2=next(itr2,1);
        map4.insert(make_pair(itr2->first,itr2->second));
        itr3=next(itr3,1);
        map4.insert(make_pair(itr3->first,itr3->second));
    }
    
    auto itr4=map4.begin();
    printf("%d",itr4->second);
    cout<<" ";
    printf("%.2f",itr4->first);
    cout<<endl;
    itr4=next(itr4,1);
    printf("%d",itr4->second);
    cout<<" ";
    printf("%.2f",itr4->first);
    cout<<endl;
}


Measured memory_bytes: 3224
function main(input) {
  const formatted_input = input.split('\n');
  const N = parseInt(formatted_input[0].split(' ')[0]);
  const Q = parseInt(formatted_input[0].split(' ')[1]);
  const S = formatted_input[1].split('');


//console.log([N,Q,S])

  var acc_arr = [0];
  var count = 0;
  for(var i=1;i<S.length;i++){
    var b=S[i-1];
    var b_1 = S[i];
    if(b=='A' && b_1=='C'){
      count++;
    }
    acc_arr.push(count);
  }

  //console.log(acc_arr);


  for(var i=0;i<Q;i++){
    var l = parseInt(formatted_input[2+i].split(' ')[0])
    var r = parseInt(formatted_input[2+i].split(' ')[1])

    console.log(acc_arr[r-1] - acc_arr[l-1])
  }

}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));



Measured memory_bytes: 36144
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
	ll n;
	cin>>n;
	ll arr[n],i=0,j=0,ans=0;
	for(i=0;i<n;i++){
		cin>>arr[i];
	}
	for(i=0;i<n;i++){
		ll temp=arr[i];
		ll var=0;
		for(j=i+1;j<n;j++){
			if(arr[j]>temp){
				break;	
			}
			else{
				temp=arr[j];
				var++;
			}
		}
		ans=max(ans,var);
		i=i+var;
	}
	cout<<ans;
}


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

//AGC

int main(){
	string s;
	cin >> s;


	int zero = 0;
	int ans = 0;
	for(int i = 0; i < (int)s.size(); i++){
		if(s[i] == '0') zero++;
		else ans += s[i] - '0';
	}

	if(s.size() == 2 and stoi(s) % 10 == 0) cout << 9 + stoi(s) / 10 << endl;
	else if(s.size() == 1) cout << s << endl;
	else if(s.size() - 1 == zero) cout << ans * 10 << endl;
	else cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
n = int(input())
ans = list(range(n+1))
for i in ans:
    if ans[i]%2!=0:
        ans[i]=0
    else:
        count = 0
        while(True):
            if ans[i]%2 != 0 or ans[i] == 0:
                ans[i] = count
                break
            else:
                ans[i]/=2
                count+=1
ans[0] = -1
print(ans.index(max(ans)))

Measured memory_bytes: 38384
N=int(input())
H=list(map(int,input().split()))
DP=[0]*N
DP[0]=0
DP[1]=abs(H[1]-H[0])
for i in range(2,N):
  DP[i]=min((abs(H[i]-H[i-1])+DP[i-1]),(abs(H[i]-H[i-2])+DP[i-2]))
print(DP[N-1])

Measured memory_bytes: 13980
import java.util.Scanner;
class Main
{
   public static void main(String[] args)
  	{
  	Scanner sc1 = new Scanner(System.in);
  	int min, max; 
        long sum;
        int n = sc1.nextInt();
        int a = sc1.nextInt();
        min = max = a;
        sum = a;
        for(int i =1; i<n; i++){
        a = sc1.nextInt();
        if(min>a) min = a;
        if(max<a) max = a;
        sum += a;
        }
        System.out.println(min+" "+max+" " +sum);
  	}
}




Measured memory_bytes: 41304
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <algorithm>
#include <random>
#define ll long long
#define fr(i,k,N) for(ll i=k; i<N;i++)
#define rep(i,N) for(ll i=0; i<N;i++)
#define alll(v) v.begin(),v.end()
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it;}cout<<endl;}

int main(){
    string s;
    ll c[3][3];
    rep(i, 3)rep(j, 3) c[i][j]=0;
    rep(i, 3)rep(j, 3) cin>>c[i][j];
    bool x = c[1][1]==c[0][1]+c[1][0]-c[0][0];
    bool y = c[1][2]==c[0][2]+c[1][0]-c[0][0];
    bool z = c[2][1]==c[0][1]+c[2][0]-c[0][0];
    bool w = c[2][2]==c[1][2]+c[2][1]-c[1][1];
    if (x & y & z & w) {
        pr("Yes");
    }else pr("No");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
 long long int a,b,c;
 cin>>a>>b>>c;
 if(a==b&&b!=c){
 	cout<<"Yes"<<endl;
 }else if(a!=b&&b==c){
 	cout<<"Yes"<<endl;
 }else if(a==c&&b!=a){
 	cout<<"Yes"<<endl;
 }else{
 	cout<<"No"<<endl;
 }


}

Measured memory_bytes: 256
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
int X;
int main(){
	cin>>X;
	int j=0;
	for(int i=1;X>0;i++){
		X-=i;
		j++;
		if(X<=0)break;
	}
		cout<<j<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
int main(){
	long long N, A, B; 
	cin >> N >> A >> B; 
	if(A % 2 == B % 2) cout << (B - A) / 2 << endl; 
	else cout << min((A + B - 1) / 2, (N * 2 - A - B + 1) / 2) << endl; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
   
using namespace std;
     
#define PB(x) push_back(x)
#define ALL(x) (x).begin(), (x).end()
#define ALLR(x) (x).rbegin(), (x).rend()
#define MP(x) make_pair(x);
    
#define debug(x) cerr << #x << '=' << x << endl;
#define debug2(x, y) cerr << #x << '=' << x << ' ' << #y << '=' << y << endl;
#define debugn(a) for (int x: a) cerr << x << ' '; cerr << endl;
#define debugm(a, h, w) for (int i = 0; i < h; i++, cout << endl) for (int j = 0; j < w; j++) cout << a[i][j] << ' ';
#define int long long
     
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef vector<string> vs;
typedef unsigned long long ull;

const int INF = 1e13;
const int mmod = 1000000007;

int32_t main()
{
	int n, m;
	cin >> n >> m;
	
	int a[n];
	for (int& x: a) cin >> x;
	
	multiset<int> st;
	for (int i = 0; i < n; i++) {
		st.insert(a[i]);
	}
	debugn(st);

	while (m > 0) {
		int v = *(st.rbegin());
		st.erase(st.lower_bound(v));
		st.insert(v/2);
		m--;
	}
	int ans = accumulate(ALL(st), 0ll);
	cout << ans << endl;
}



Measured memory_bytes: 5760
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,w,h;
	while(1){
		cin >> n >> w >> h;
		if(n==0&&w==0&&h==0)break;
		vector<pair<int,int>> v;
		v.push_back({w,h});
		for(int i=0;i<n;i++){
			int p,s; cin >> p >> s;
			auto ca=v[p-1];
			v.erase(v.begin()+p-1);
			int ww=ca.first,hh=ca.second;
			s%=(ww+hh+ww+hh);
			pair<int,int> p1,p2;
			if(0<s&&s<ww){
				p1=make_pair(s,hh);
				p2=make_pair(ww-s,hh);
			}
			else if(ww<s&&s<ww+hh){
				p1=make_pair(ww,s-ww);
				p2=make_pair(ww,hh-(s-ww));
			}
			else if(ww+hh<s&&ww+hh+ww>s){
				p1=make_pair(s-ww-hh,hh);
				p2=make_pair(ww-(s-ww-hh),hh);
			}
			else{
				p1=make_pair(ww,s-ww-hh-ww);
				p2=make_pair(ww,hh-(s-ww-hh-ww));
			}
			if(p1.first*p1.second>p2.first*p2.second){
				swap(p1,p2);
			}
			v.push_back(p1);
			v.push_back(p2);
		}
		sort(v.begin(), v.end(),[](auto i,auto j){
			return i.first*i.second<j.first*j.second;
		});
		for(int i=0;i<v.size();i++){
			if(i)printf(" ");
			printf("%d",v[i].first*v[i].second);
		}
		printf("\n");
	}
}



Measured memory_bytes: 3112
a,b,c,x,y,f,t;main(n){while(1){scanf("%d%d%d%d%d",&n,&a,&b,&c,&x);if(!n)exit(0);for(f=t=0;n-->0;){scanf("%d",&y);while(t||x!=y&&f<10001)t=0,f++,x=(a*x+b)%c;t=1;}if(f>10000)f=-1;printf("%d\n",f);}}

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

namespace D___Ki
{
    class Program
    {
        static void Main(string[] args)
        {
            var NQ = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            var N = NQ[0];
            var Q = NQ[1];
            var connections = new List<int>[N + 1];
            for (int i = 0; i < N + 1; i++) connections[i] = new List<int>();
            for (int i = 0; i < N - 1; i++)
            {
                var ab = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                connections[ab[0]].Add(ab[1]);
                connections[ab[1]].Add(ab[0]);
            }

            var counter = new long[N];
            for (int i = 0; i < Q; i++)
            {
                var px = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
                counter[px[0] - 1] += px[1];
            }

            var isSearch = new bool[N + 1];
            for (int i = 0; i < N + 1; i++) isSearch[i] = false;
            var queue = new Queue<int>();
            queue.Enqueue(1);
            while (queue.Count != 0)
            {
                var current = queue.Dequeue();
                isSearch[current] = true;
                foreach (int child in connections[current])
                {
                    if (isSearch[child]) continue;
                    counter[child - 1] += counter[current - 1];
                    queue.Enqueue(child);
                }
            }
            Console.WriteLine(string.Join(" ", counter));
        }
    }
}


Measured memory_bytes: 51824
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    int dp[n+1];
    dp[0]=0;
    dp[1]=abs(arr[1] -arr[0]);
    for(int i=2;i<n;i++)
    {
        dp[i]=min(abs(arr[i-2]-arr[i])+dp[i-2],abs(arr[i-1]-arr[i])+dp[i-1]);
    }
    cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>

#define Mod 1000000007

typedef struct List {
	struct List *next;
	int v;
} list;

int main()
{
	int i, N, P[5001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &(P[i]));
	
	list **adj = (list**)malloc(sizeof(list*) * (N + 1)), *d = (list*)malloc(sizeof(list) * N * 2);
	for (i = 0; i < N; i++) {
		if (P[i+1] == -1) continue;
		d[i*2].v = P[i+1];
		d[i*2+1].v = i + 1;
		d[i*2].next = adj[i+1];
		d[i*2+1].next = adj[P[i+1]];
		adj[i+1] = &(d[i*2]);
		adj[P[i+1]] = &(d[i*2+1]);
	}
	
	list *p;
	int j, k, K, comp[5001] = {}, q[5001], head, tail, size[5001] = {};
	for (i = 1, k = 1; i <= N; i++) {
		if (P[i] != -1) continue;
		comp[i] = k;
		q[0] = i;
		for (head = 0, tail = 1; head < tail; head++) {
			for (p = adj[q[head]]; p != NULL; p = p->next) {
				if (comp[p->v] == 0) {
					comp[p->v] = k;
					q[tail++] = p->v;
				}
			}
		}
		size[k++] = tail;
	}
	for (i = 1, K = k - 1; i <= N; i++) {
		if (comp[i] != 0) continue;
		comp[i] = k;
		q[0] = i;
		for (head = 0, tail = 1; head < tail; head++) {
			for (p = adj[q[head]]; p != NULL; p = p->next) {
				if (comp[p->v] == 0) {
					comp[p->v] = k;
					q[tail++] = p->v;
				}
			}
		}
		k++;
	}
	
	int l;
	long long ans = N - k + 1 + K, dp[2][5001] = {{1}}, N_pow[5001] = {1}, fact;
	for (i = 1; i <= K; i++) {
		l = i % 2;
		N_pow[i] = N_pow[i-1] * (N - 1) % Mod;
		dp[l][0] = dp[1-l][0] * size[i] % Mod;
		for (j = 1; j <= i; j++) dp[l][j] = (dp[1-l][j-1] + dp[1-l][j] * size[i]) % Mod;
	}
	ans = (ans * N_pow[K] - (dp[K%2][K-1] - K) * N_pow[K-1] % Mod) % Mod;
	for (i = 2, fact = 1; i <= K; i++, fact = fact * (i - 1) % Mod) {
		ans = (ans + Mod - ((dp[K%2][K-i] * fact % Mod) * N_pow[K-i] % Mod)) % Mod;
	}
	
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 2108
#include<bits/stdc++.h>
using namespace std;
int mod;
int add(int x,int y){return x+y<mod?x+y:x+y-mod;}
void ade(int& x,int y){x+=y;if(x>=mod)x-=mod;}
int n,m;
struct Solve1{
    int dp[155][155];
    void run()
    {
        dp[0][0]=1;
        for(int i=1;i+i<=n+1;++i)
            for(int j=0;j+j<=m;++j)
            {
                ade(dp[i][0],dp[i-1][j]);
                if(j) ade(dp[i][j],dp[i-1][j-1]);
            }
        for(int i=1;i<=m/2;++i)ade(dp[n/2][i],dp[n/2][i-1]);
        if(n&1)
            for(int i=1;i<=m/2;++i)ade(dp[(n+1)/2][i],dp[(n+1)/2][i-1]);
        printf("%lld\n",1ll*dp[n/2][m/2]*dp[(n+1)/2][m/2]%mod);
    }
}solve1;
struct Solve2{
    int dp[155][155][155];
    void run()
    {
        dp[0][0][0]=1;
        int l,r;
        bool inl,inr;
        for(int i=1;i<=n;++i)
        {
            r=i*2;l=r-m;
            inl=(l>=1&&l<=n);
            inr=(r>=1&&r<=n);
            for(int j=0;j<=n;++j)
                for(int k=0;k<=m+1;++k)
                {
                    ade(dp[i][0][0],dp[i-1][j][k]);
                    if(inr)//选择当前行右边的点
                        ade(dp[i][j+1][0],dp[i-1][j][k]);
                    if(inl&&k+1<=m+1)//选择当前行左边的点
                        ade(dp[i][0][k?k+1:0],dp[i-1][j][k]);
                    if(inl&&inr&&max(j+2,k+1)<=m+1)//两边一起选
                        ade(dp[i][j+1][max(j+2,k+1)],dp[i-1][j][k]);
                }
        }
        printf("%d\n",dp[n][0][0]);
    }
}solve2;
int main()
{
    scanf("%d%d%d",&n,&m,&mod);
    if(m&1)solve2.run();
    else solve1.run();
    return 0;
}


Measured memory_bytes: 14464
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pp;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> super_set;

#define x1 dfds
#define y1 dsfdsfe
#define pb push_back
#define forn(i,n) for(ll i = 1;i<=n;++i)
#define fi first
#define sc second
#define endl '\n'
#define po(x) (1ll<<x)
const ll DIM = 50+7;
const ll INF = 10E17;
const ll MOD = 2019;
ll binpow(ll x,ll power){
    ll mult = x%MOD;
    x = 1;
    while(power>0){
        if (power&1)x = (x*mult)%MOD;
        mult = (mult*mult)%MOD;
        power/=2;
    }
    return x;
}
ll gi(char ch){
    return ch-'0';
}
int main()
{

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s;
    cin>>s;
    ll mult = 1;
    ll n = s.length();

    map<ll,ll> M;
    ll pref = 0;
    ll res = 0;
    M[0] = 1;
    reverse(s.begin(),s.end());
    mult = 1;
    for(ll i = 0;i<n;++i){
        pref = (pref+gi(s[i])*mult)%MOD;
        res+=M[pref];
        M[pref]++;
        mult = (mult*10)%MOD;
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 3772
#include <iostream>
#include <string.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

int n,num,a[100010];

ll qp2(ll x) {
    ll ret=1;
    ll tmp=2;
    while (x) {
        if (x&1) {
            ret=(ret*tmp)%MOD;
        }
        tmp=(tmp*tmp)%MOD;
        x>>=1;
    }
    return ret;
}

int main() {
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    for (int i=0;i<n;i++) {
        scanf("%d",&num);
        a[num]++;
    }
    if (n&1) {
        if (a[0]!=1) {
            printf("0\n");
            return 0;
        }
        for (int i=2;i<n;i+=2) {
            if (a[i]!=2) {
                printf("0\n");
                return 0;
            }
        }
    } else {
        for (int i=1;i<n;i+=2) {
            if (a[i]!=2) {
                printf("0\n");
                return 0;
            }
        }
    }
    ll ans=qp2(n/2);
    printf("%lld\n",ans);
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define MOD 1000000007
using namespace std;
int main()
{

char c;
ll i,j,n;
vector <ll> v;
vector <char> v1;
string s;
cin>>s;
n=s.length();
for(i=0;i<n;i++)
{
    // c=s[i];
    ll cnt=1;
    v1.pb(s[i]);
    while(i<n&&s[i]==s[i+1])
    {
        i++;
        cnt++;
    }
    v.pb(cnt);
    
}
n=v.size();
ll sum=0;
// for(auto it:v1)
//     cout<<it<<" ";
// cout<<endl;
// for(auto it:v)
//     cout<<it<<" ";
// cout<<endl;

for(i=0;i<n-1;i++)
{
    if(v1[i]=='<'&&v1[i+1]=='>')
    {
        if (v[i] < v[i + 1])
            v[i]--;
        else
            v[i + 1]--;
    }
        sum = sum + (v[i] * (v[i] + 1)) / 2;
        // cout<<v[i]<<" "<<sum<<"\n";
}
sum = sum + (v[i] * (v[i] + 1)) / 2;
cout<<sum;


return 0;
}


Measured memory_bytes: 3196
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

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

macro_rules! read_value {
    ($next:expr, [graph1; $len:expr]) => {{
        let mut g = vec![vec![]; $len];
        let ab = read_value!($next, [(usize1, usize1)]);
        for (a, b) in ab {
            g[a].push(b);
            g[b].push(a);
        }
        g
    }};
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
    ($next:expr, usize1) => (read_value!($next, usize) - 1);
    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        read_value!($next, [$t; len])
    }};
    ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        n: usize, k: usize,
        p: [i64; n],
    }
    let mut p = p;
    p.sort();
    puts!("{}\n", p[..k].iter().sum::<i64>());
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 2296
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func rScan() []rune {
	return []rune(Scan())
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func mod(x, d int) int {
	x %= d
	if x < 0 {
		x += d
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}
func fSum(a []float64) float64 {
	x := 0.
	for _, v := range a {
		x += v
	}
	return x
}
func bPrint(f bool, x string, y string) {
	if f {
		fmt.Println(x)
	} else {
		fmt.Println(y)
	}
}
func iSSPrint(x []int) {
	fmt.Println(strings.Trim(fmt.Sprint(x), "[]"))
}

var lp1 int = 1000000007
var lp2 int = 998244353

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, lp1)
	sc.Split(bufio.ScanWords)
	n, q := iScan(), iScan()
	uf := newUnionFind(n)
	for i := 0; i < q; i++ {
		t, u, v := iScan(), iScan(), iScan()
		if t == 0 {
			uf.unite(u, v)
		} else {
			bPrint(uf.same(u, v), "1", "0")
		}
	}
}

type UnionFind struct {
	n   int
	par []int
}

func newUnionFind(n int) *UnionFind {
	uf := new(UnionFind)
	uf.n = n
	uf.par = make([]int, n)
	for i, _ := range uf.par {
		uf.par[i] = -1
	}
	return uf
}
func (uf UnionFind) root(x int) int {
	if uf.par[x] < 0 {
		return x
	}
	uf.par[x] = uf.root(uf.par[x])
	return uf.par[x]
}
func (uf UnionFind) unite(x, y int) {
	rx, ry := uf.root(x), uf.root(y)
	if rx != ry {
		if uf.size(rx) > uf.size(ry) {
			rx, ry = ry, rx
		}
		uf.par[ry] += uf.par[rx]
		uf.par[rx] = ry
	}
}
func (uf UnionFind) same(x, y int) bool {
	return uf.root(x) == uf.root(y)
}
func (uf UnionFind) size(x int) int {
	return -uf.par[uf.root(x)]
}
func (uf UnionFind) groups() [][]int {
	rootBuf, groupSize := make([]int, uf.n), make([]int, uf.n)
	for i := 0; i < uf.n; i++ {
		rootBuf[i] = uf.root(i)
		groupSize[rootBuf[i]]++
	}
	res := make([][]int, uf.n)
	for i := 0; i < uf.n; i++ {
		res[i] = make([]int, 0, groupSize[i])
	}
	for i := 0; i < uf.n; i++ {
		res[rootBuf[i]] = append(res[rootBuf[i]], i)
	}
	result := make([][]int, 0, uf.n)
	for i := 0; i < uf.n; i++ {
		if len(res[i]) != 0 {
			r := make([]int, len(res[i]))
			copy(r, res[i])
			result = append(res, r)
		}
	}
	return result
}


Measured memory_bytes: 6008
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define LL long long
#define PP pair<LL,LL>
int N;
vector<PP> AB;
LL ans = 0;
int main(){
 	cin >> N;
	AB.push_back(PP{0, 0});
	for(int i = 0; i < N; i++){
		LL tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		AB.push_back(PP{tmp1, tmp2});
	}

	sort(AB.begin(), AB.end());
	
	for(int i = 1; i <= N; i++){
		AB[i].second += AB[i - 1].second;
	}

	LL minimum = AB[0].second - AB[1].first;
	for(int i = 1; i <= N; i++){
		LL r = AB[i].second - AB[i].first;
		minimum = min(minimum, AB[i - 1].second - AB[i].first);
		ans = max(ans, r - minimum);
	}

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


Measured memory_bytes: 11208
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int size=1e4;
const long inf=1e9;
int main(){
	int N;cin>>N;
	cout<<(N+1)/2<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
int a;
  int b;
  cin >>a>>b;
  if((a+b)%2==0) {
cout << (a+b)/2 << endl;
  }
else {
cout << (a+b)/2+1 << endl;
}
}

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

long long x, k, d;

int main() {
	scanf("%lld%lld%lld", &x, &k, &d);
	x = abs(x);
	long long pos = x % d;
	if ((x - pos) / d > k) {
		printf("%lld\n", x - d * k);
	} else {
		if (((x - pos) / d) % 2 == (k % 2)) printf("%lld\n", pos);
		else printf("%lld\n", (long long) abs(pos - d));
	}
	return 0;
}


Measured memory_bytes: 3824
#include <stdio.h>

int main(){

  int sum,i;
  char s[1001];
  while(1){
    scanf("%s",s);
    if(s[0]=='0')break;
    sum=0;
    i=0;
    while(s[i]){
      sum += s[i]-'0';
      i++;
    }
    printf("%d\n",sum);
  }
  return 0;
}

Measured memory_bytes: 536
while ((n,x = gets.split(" ").map(&:to_i)).inject(:+) != 0) do
  r = []
  n.downto(1) do |n1|
    (n1-1).downto(1) do |n2|
      (n2-1).downto(1) do |n3|
        r<<[n1,n2,n3] if ((n1 + n2 + n3) == x)
      end
    end
  end
  puts r.length
end

Measured memory_bytes: 8740
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(obj) (obj).begin(),(obj).end() 
#define dump(x)  cout << #x << " = " << (x) << endl;
typedef long long lint;
using namespace std;
int main(){
	int n,num=0;
	cin>>n;
	vector<int>p(n);
	rep(i,n)cin>>p.at(i);
	rep(i,n-1)if(p.at(i)!=i+1)num++;
	cout<<(num<=2?"YES":"NO")<<endl;
}


Measured memory_bytes: 256
N = int(input())
B = list(map(int, input().split()))
B.append(B[N-2])

ans = 0
# A = []
for i in range(N)[::-1]:
    if i == 0:
        ans += B[i]
        # A.append(B[i])
    else:
        ans += min(B[i-1], B[i])
        # A.append(min(B[i-1], B[i]))

# print(A)
print(ans)


Measured memory_bytes: 2940