akhauriyash/Code-Regression huggingface dataset:
// skip until line 65
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <istream>
#include <iterator>
#include <sstream>
#include <list>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

#define BR "\n"
#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define ALL(cont) begin(cont),end(cont)
#define AS_MOD(a, b) ((((a) % (b) ) + (b)) % (b))
#define MO(a) AS_MOD(a,mod)
#define FEACH(it, cont) for(auto (it) = begin(cont); it!=end(cont);++it)
#define FEACHR(it, cont) for(auto (it) = rbegin(cont); it!=rend(cont);++it)
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define getll() ([](){ll s;scanf("%lld", &s);return s;})()
#define getld() ([](){ld s;scanf("%Lf", &s);return s;})()
#define prl(P) printf("%lld", P)
#define prd(P) printf("%.10Lf", P)
#define pr(P) printf(P)
#define MAX(V, T) V=max(V,T)
#define MIN(V, T) V=min(V,T)

#define PrintArray(cont, from, to) for(int __i=from;__i<to;++__i) {cout<<"(" <<__i<<": " << cont[__i]<<")";} cout<<endl;
#define PrintPairs(cont, from, to) for(int __i=from;__i<to;++__i) {cout<<"(" <<__i<<": " << cont[__i].fi <<"," << cont[__i].se<<")";} cout<<endl;
#define Print(v) cout<<v<<endl;
#define PrintArray2D(cont, fh, th, fw, tw) for(int __i=fh;__i<th;++__i){for(int __j=fw;__j<tw;++__j) {cout<<cont[__i][__j]<<" ";} cout<<endl;}cout<<endl;
/*
 * ***_bound(6)
 * 5 6 6 6 6 6 7 7 7
 *   ^lower    ^upper
 * void reverse(c.begin(), c.end())
 *
 * graph
 * seg tree
 * dp
 * brute force
 * priority_queue<int,vector<int>, greater<int>> Q;
 */
struct Comparator{
    int operator()(int l, int r) const {
        return r<l;
    }
};
struct Vec;
//set<int, Comparator> S;

// solution below
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
int main() {
    cout.precision(15);
    cout << fixed;
    int N;
    vector<bool> Db(1000*1000+10,false);
    vector<int>A;
    cin>>N;
    A.resize(N);
    REP(i,N)
        cin>>A[i];
    sort(ALL(A));
    int ans=0;
    REP(i,N) {
        if (i>0 && A[i-1]==A[i])continue;
        if (!Db[A[i]] && !(i<N-1 && A[i]==A[i+1]))ans++;
        int target=A[i];
        while(target<=1000*1000) {
            Db[target]=true;
            target+=A[i];
        }
    }
    cout<<ans<<endl;


}


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

int main(void)
{
	int N;
	cin >> N;

	while(N > 0){
		int data[10];
		int a=0,b=-1;
		for(int i = 0; i < 10; i++){
			cin >> data[i];

		}

		for(int i = 0; i < 10; i++){
			if(a > data[i] && b > data[i]){
				a = -1;
				break;
			}
			if(data[i] > a && a > b)
				a = data[i];
			else if(a > data[i] && data[i] > b)
				b = data[i];


		}

		if(a < 0)
			cout << "NO" << endl;
		else
			cout << "YES" << endl;

		N--;
	}

	return 0;

}

Measured memory_bytes: 1152
#include <stdio.h>

int main(void) {

  int A,B,C;

  scanf("%d%d", &A, &B);

  if( A % 3 == 0 || B % 3 == 0 || (A+B) % 3 == 0)
    printf("Possible\n");
  else
    printf("Impossible\n");
  
  return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main{
  public static void main(String args[]){
    Scanner scan = new Scanner(System.in);
    int r = scan.nextInt();
    if(r < 1200){
      System.out.println("ABC");
    }else if(r < 2800){
      System.out.println("ARC");
    }else{
      System.out.println("AGC");
    }
  }
}


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

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

    int length = s.size();
    for (int tsumugi = 0; tsumugi < length; tsumugi ++){
        if (tsumugi % 2 == 0){  //奇数文字の時
            if (s[tsumugi] == 'L'){
                cout << "No" << endl;
                return 0;
            }
        }
        else{   //偶数文字の時
            if (s[tsumugi] == 'R'){
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;
    return 0;
}

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

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define RREP(i, a, b) for (int i = (int)(a)-1; i >= (int)(b); --i)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, n, 0)
#define ALL(r) (r).begin(), (r).end()

void Main();

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

void Main() {
    int n, k, d, a, r = 0; cin >> n >> k;
    vector<bool> snuke(n, false);
    rep(i, k) {
        cin >> d;
        rep(j, d) {
            cin >> a;
            snuke[a-1] = true;
        }
    }
    rep(i, n) {
        if (!snuke[i]) {
            r++;
        }
    }
    cout << r << endl;
}


Measured memory_bytes: 3588
#include <iostream>
#include <string>

using namespace std;

int main(){
    int N;
    string s;
    cin>>N;
    cin>>s;
    int r=0;
    int b=0;
    for(int i=0;i<N;i++){
        if (s[i]=='R') r++;
        else b++;
    }
    if(r>b) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
/* ****revpro**** */
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl     '\n'
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)    
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define mii      map<ll,ll>
using namespace std;

#define N  100005
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;  
#define ordered_set tree<double, null_type,less<double>, rb_tree_tag,tree_order_statistics_node_update> 
signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int TESTS=1;
//  cin>>TESTS;
  while(TESTS--)
  {
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll pre=s[0];
    ll ans=0;
    rep(i,0,n){
      if(s[i]!=pre){
        ans++;
        pre=s[i];
      }
    } 
    ans++;
    cout<<ans;
  }
  return 0;
}

Measured memory_bytes: 512
"use strict"
function main(arg) {
    var data = arg.trim().split("\n")[0]
    data = data.split('hi').join('')
    if (data.length > 0) {
        console.log('No')
    } else {
        console.log('Yes')
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 22076
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef unsigned long long ul;

int x[3], n;
int c[3];
ll ans;
bool used[1 << 17];
ll a[1 << 17][3];

typedef pair<ll, P> speP;
priority_queue<LP> q;
int main() {
	rep(i, 3) {
		cin >> x[i]; n += x[i];
	}
	rep(i, n) {
		rep(j, 3) {
			cin >> a[i][j];
		}
	}
	rep(i, n) {
		ans += a[i][2];
		rep(j, 2) {
			a[i][j] -= a[i][2];
		}
	}
	rep(i, n) {
		q.push({ a[i][1],i });
	}
	ll ma = -INF;
	priority_queue<ll> que;
	priority_queue<LP>que2,que3;
	rep(i, x[1]) {
		LP z = q.top(); q.pop();
		ans += z.first;
		que.push(a[z.second][0] - z.first);
		used[z.second] = true;
	}
	rep(i, n) {
		if (used[i])continue;
		que2.push({ a[i][0],i });
		que3.push({ a[i][1],i });
	}
	rep(i, x[0]) {
		while (used[que3.top().second])que3.pop();
		while (used[que2.top().second])que2.pop();
		ll vl = que.top() + que3.top().first;
		ll vr = que2.top().first;
		if (vl < vr) {
			ans += vr;
			used[que2.top().second] = true;
			que2.pop();
		}
		else {
			ans += vl;
			que.pop();
			LP z = que3.top();
			que.push(a[z.second][0] - z.first);
			used[z.second] = true;
			que3.pop();
		}
	}
	cout << ans << endl;

	//stop
	return 0;
}

Measured memory_bytes: 9456
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>

typedef int32_t i32;
typedef int64_t i64;

#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))

void run (void) {
  i32 n;
  i64 k;
  scanf ("%" SCNi32 "%" SCNi64, &n, &k);
  i32 *a = ALLOC (n, i32);
  for (i32 i = 0; i < n; ++i) {
    scanf ("%" SCNi32, a + i);
  }
  const i32 m = 200000;
  i64 *next = ALLOC (2 * n, i64);
  i64 *memo = ALLOC (m + 1, i64);
  for (i32 i = 2 * n - 1; i >= 0; --i) {
    i32 x = i % n;
    next[i] = memo[a[x]];
    memo[a[x]] = i;
  }
  for (i32 i = 0; i < n; ++i) {
    next[i] = next[i] - i + 1;
  }
  memcpy (memo, next, sizeof (i64) * n);
  i64 *tmp = ALLOC (n, i64);
  i64 now = 0;
  for (;;) {
    memcpy (next, memo, sizeof (i64) * n);
    for (;;) {
      for (i32 i = 0; i < n; ++i) {
        tmp[i] = next[(i + next[i]) % n] + next[i];
      }
      if (now + tmp[now % n] >= n * k) break;
      memcpy (next, tmp, sizeof (i64) * n);
    }
    if (now + next[now % n] >= n * k) break;
    now += next[now % n];
  }
  uint8_t *elem = ALLOC (m + 1, uint8_t);
  i32 *ans = ALLOC (n, i32);
  i32 len = 0;
  for (i64 i = now; i < n * k; ++i) {
    i32 x = i % n;
    if (elem[a[x]]) {
      while (ans[len - 1] != a[x]) {
        elem[ans[--len]] = 0;
      }
      elem[ans[--len]] = 0;
    } else {
      ans[len++] = a[x];
      elem[a[x]] = 1;
    }
  }
  for (i32 i = 0; i < len; ++i) {
    printf ("%" PRIi32, ans[i]);
    putchar (i == len - 1 ? '\n' : ' ');
  }
}

int main (void) {
  run();
  return 0;
}


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

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

#define CIN(T, x) T x; cin >> x;


int main() {

    CIN(string, S);

    int ans = 0;
    for (int i = 0; i < S.size(); i++) {
        if ( S[i] == '1' )  ans++;
    }

    cout << min(ans, (int)S.size() - ans) * 2 << "\n";
    return 0;
}

Measured memory_bytes: 512
import itertools
n = int(input())
p = tuple([i-1 for i in map(int, input().split())])
q = tuple([i-1 for i in map(int, input().split())])

for i, item in enumerate(itertools.permutations(range(n))):
    if item == p:
        a = i
    if item == q:
        b = i
print(abs(a - b))


Measured memory_bytes: 39024
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

typedef pair<int,int>pi;
typedef vector<int>vi;

const int MAXN=100005;
const int MOD=1000000007;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())
#define UP(v,x) (upper_bound(all(v),(x))-(v).begin())

main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N; cin >> N;
	map<string, int> freq;
	FOR(i,1,N){
		string S; cin >> S;
		freq[S]++;
	}
	cout <<  "AC x " << freq["AC"] << "\n";
	cout <<  "WA x " << freq["WA"] << "\n";
	cout <<  "TLE x " << freq["TLE"] << "\n";
	cout <<  "RE x " << freq["RE"] << "\n";
}


Measured memory_bytes: 3664
#include<stdio.h>

int main(){
  int K, S, i, j, k, count = 0;
  scanf("%d %d", &K, &S);
  for (i = 0; i <= K; i++){
    for (j = 0; j <= K; j++){
      if(S - i - j < 0){
        break;
      }
      if(S - i - j <= K){
        count++;
      }
    }
  }
  
  printf("%d\n", count);
  
  return 0;
}

Measured memory_bytes: 128
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
string s; int c[33];
int main() {
	cin >> s;
	for (char cs : s) c[cs - 97]++;
	int ptr = -1;
	for (int i = 0; i < 26; i++) {
		if (c[i] == 0) {
			ptr = i;
			break;
		}
	}
	if (ptr == -1) cout << "None" << endl;
	else cout << (char)(ptr + 97) << endl;
	return 0;
}

Measured memory_bytes: 512
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
int ans[100005][200];
using namespace std;
string SS[200000];
int main(){
    int N;
    cin>>N;
    ans[0][0]=1;

    for(int i=0;i<N;i++){
        cin>>SS[i];
        if(SS[i]=="0"){
            puts("0");
            return 0;
        }
    }
    for(int i=0;i<N;i++){
        string S;
        S=SS[i];
        if(S=="0"){
            puts("0");
            return 0;
        }
        for(int j=0;j<100;j++){
            for(int k=0;k<S.size();k++){
                ans[i+1][j+(S.size()-1-k)]+=ans[i][j]*(S[k]-'0');
            }
        }
        for(int j=0;j<180;j++){
            ans[i+1][j+1]+=ans[i+1][j]/10;
            ans[i+1][j]=ans[i+1][j]%10;
            if(20<j&&ans[i+1][j]!=0){
                cout<<-1<<endl;
                return 0;
            }
        }
    }

    for(int i=0;i<100005;i++){
        for(int j=0;j<180;j++){
            ans[i][j+1]+=ans[i][j]/10;
            ans[i][j]=ans[i][j]%10;
        }
    }
/*
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            printf("[%d]",ans[i][j]);
        }
        puts("");
    }
*/


    int flg=0;
    for(int i=180;0<=i;i--){
        if(flg||ans[N][i]!=0){
            if(18<i){
                cout<<-1<<endl;
                return 0;
            }
            if(i==18){
                int flgflg=0;
                for(int j=0;j<18;j++){
                    if(ans[N][j]!=0)flgflg=1;
                }
                if(flgflg==1){
                    cout<<-1<<endl;
                    return 0;
                }
            }
            cout<<ans[N][i];
            flg=1;
        }
    }
    if(flg==0)cout<<0;
    cout<<endl;
    return 0;
}


Measured memory_bytes: 88008
#include<iostream>

using namespace std;

int main()
{
        string input;
        int num = 0;
        int i = 0;
        int count = 0;
        char temp[1];

        cin >> input;
        num = input.size();
        char str[num]; //= input.toCharArray(); 

        sprintf(str,"%s",input.c_str());

        if(num % 2 == 0)
        {
                count = num / 2;
        }
        else
        {
                count = (num - 1) / 2;
        }

        for(i = 0;i < count;i++)
        {
                temp[0] = str[i];
                str[i] = str[num -  1 - i];
                str[num - 1 - i] = temp[0];
        }

        string output = string(str);
        cout << output << endl;

}

Measured memory_bytes: 1200
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			int[] vs = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
			int N = vs[0];
			int D = vs[1];

			int ans = N / (2 * D + 1);
			if (N % (2 * D + 1) > 0) {
				ans += 1;
			}
			Console.WriteLine(ans);
		}
	}
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define repr(i, n) for(int i = n;i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793
#define MOD 1000000007

typedef long long ll;

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

    int n,a,b,ans = 0;
    cin >> n;
    rep(i,n){
        cin >> a >> b;
        ans += b - a + 1;
    }

    cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sort(v) sort(v.begin(),v.end())
#define pb push_back
/*
ll ar[10000+9]={0};
void seiv()
{
ll n=10000+9,i,j;
ar[1]=1;
for(i=4;i<=n;i+=2)ar[i]=1;
for(i=3;i<=n;i+=2)
{
if(ar[i]==0)
{
for(j=i*i;j<=n;j+=i*2)ar[j]=1;
}
}
}*/
int main()
{
    ll a,b;
  cin>>a>>b;
  if(a<=9&&b<=9)cout<<a*b<<endl;
else cout<<-1;
 }

Measured memory_bytes: 3632
(declaim (inline calc))
(defun calc (x y)
  (let ((diff (- y (* x 2))))
    (let* ((turtle (/ diff 2))
           (crane (- x turtle)))
      (cond ((or (oddp y) (< turtle 0) (< crane 0))
             "No")
            ((= x (+ turtle crane))
             "Yes")
            (t "No")))))

(princ (calc (read) (read)))


Measured memory_bytes: 24572
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <tuple>
#include <bitset>
#include <random>

int money[300];

int main(){
  int x, y;
  std::cin >> x >> y;
  int ans = 0;
  money[1]=300000;
  money[2]=200000;
  money[3]=100000;
  ans += money[x];
  ans += money[y];
  if (x==y && x==1){
    ans += 400000;
  }
  std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 3160
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>
#include <complex>

using namespace std;

#define mod 1000000007

int main()
{
	int n;
	cin >> n;
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		int p;
		cin >> p;
		if(p != i) cnt++;
	}
	if(cnt <= 2) cout << "YES" << endl;
	else cout << "NO" << endl;


}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){

  int N;
  int K;
  int Q;
  cin>>N>>K>>Q;
  vector<int>playerdata(N);
  for(int i=0;i<=N-1;i++){
  
    playerdata[i]=K;
  }
  vector<int>gamedata(Q);
  for(int i=0;i<=Q-1;i++){
  
    cin>>gamedata[i];
  }
  for(int i=0;i<=N-1;i++){
  
    playerdata[i]-=Q;
  }
  for(int i=0;i<=Q-1;i++){
  
    playerdata[gamedata[i]-1]++;
  }
  for(int i=0;i<=N-1;i++){
  
    if(playerdata[i]<=0){
    
      cout<<"No"<<endl;
    }
    else{
    
      cout<<"Yes"<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3996
#include <bits/stdc++.h>  
using namespace std;  
typedef long long LL;  
  
int DigitSum(LL n) {  
    int res = 0;  
    while(n > 0) {  
        res += n % 10;  
        n /= 10;  
    }  
    return res;  
}  
int main(void) {  
    LL n, temp;  
    cin >> n;  
    int ans = DigitSum(n);  
    temp = n;  
    LL cnt = 1;  
    while(temp >= 10) {  
        temp /= 10;  
        cnt *= 10;  
    }  
    ans = max(ans, DigitSum(n / cnt * cnt - 1));  
    cout  << ans << endl;  
    return 0;  
}  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
using ll = long long;
int main(){
	int N;
	cin>>N;
	vector<ll> a(N);
	rep(i,N) cin>>a[i];
	set<ll> st;
	ll ans = 0;
	ll offset = 0;
	for(int i=N-1;i>=0;i--){
		st.insert(a[i]-offset);
		if(*st.rbegin() != a[i]-offset){
			puts("-1");
			return 0;
		}
		while(!st.empty() && *st.begin()+offset <= 0) st.erase(st.begin());
		ans += st.size();
		offset--;
	}
	if(!st.empty()) puts("-1");
	else cout<<ans<<endl;
}


Measured memory_bytes: 6528
#!/usr/bin/env python3
import sys
from collections import deque
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, S: "List[str]"):

    counter = 1
    s1, s2 = S
    pre = 0
    i = 0
    while i < N:
        if s1[i] == s2[i]:
            counter *= 3-pre
            counter %= MOD
            i += 1
            pre = 1
        else:
            if pre == 0:
                counter *= 6
                counter %= MOD
            elif pre == 1:
                counter *= 2
                counter %= MOD
            else:
                counter *= 3
                counter %= MOD

            i += 2
            pre = 2

    print(counter)

    return


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) for _ in range(2)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
 
        int[][] list = new int[a][b];
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                list[i][j] = scanner.nextInt();
            }
        }
        int[] list2 = new int[b];
        for (int i = 0; i < b; i++) {
            list2[i] = scanner.nextInt();
        }
        int sum;
        for (int i = 0; i < a; i++) {
            sum = 0;
            for (int j = 0; j < b; j++) {
                sum += list[i][j] * list2[j];
            }
            System.out.println(sum);
        }
 
    }
}


Measured memory_bytes: 40308
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <set>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

map< int64_t, int64_t > prime_factor(int64_t n) {
  map< int64_t, int64_t > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int main(){
    ll n;
    cin >> n;
    auto pf = prime_factor(n-1);
    vector<ll> vec;
    ll ans = 1;

    for(auto e:pf){
        ans *= (e.second+1);
    }
    ans--;


    for(ll i=1; i * i<=n; i++){
        if(n % i == 0){
            //cout << i << " " << n/i << endl;
            vec.push_back(i);
            if(i!=1 && i*i != n) vec.push_back(n/i);
        }
    }

    for(auto e: vec){
        //cout <<e << endl;
        if(e == 1) continue;
        ll tmp = n;
        while(tmp % e == 0){
            tmp /= e;
        }
        if(tmp % e == 1){
            ans++;
        }
    }

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


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

int main() {
  int n; cin >> n;
  unordered_map<int, int> mp;
  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    mp[x]++;
  }
  long long ans = 0;
  for (auto p : mp) {
    int sum = p.second - p.first;
    if (p.second < p.first) {
      sum = p.second;
    }
    ans += sum;
  }
  cout << ans;
}


Measured memory_bytes: 7176
"""
"""


def int_as_array(num): return list(map(int, [y for y in str(num)]))


def array_as_int(arr): return int(''.join(map(str, arr)))


def read_int(): return int(input())


def read_array(): return list(map(int, input().split(' ')))


def array_to_string(arr, sep=' '): return sep.join(map(str, arr))


def matrix_to_string(arr, sep=' '): return '[\n' + '\n'.join(
    [sep.join(map(str, row)) for row in arr]) + '\n]'


def solve(string):
    if string != string[::-1]:
        return False
    first = string[0:(len(string) - 1) // 2]
    if first != first[::-1]:
        return False
    second = string[(len(string) + 2) // 2:]
    if second != second[::-1]:
        return False
    return True


string = input()
if solve(string):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include <climits>
#include <string>
using namespace std;

int a[100],b[100];
int dp[100][100];
 
int main(){
    int n,i,j,k;
    cin >> n;
    for(i=0;i<n;i++) cin >> a[i] >> b[i];
    for(i=0;i<n;i++) for(j=0;j<n;j++) dp[i][j] = INT_MAX;
    for(i=0;i<n;i++) dp[i][i] = 0;
    for(i=2;i<=n;i++){
        for(j=0;j<=n-i;j++){
            for(k=j+1;k<j+i;k++){
                dp[j][j+i-1] = min(dp[j][j+i-1] , dp[j][k-1] + dp[k][j+i-1] + a[j] * b[k-1] * a[k] * b[j+i-1]);
            }
        }
    }
    cout << dp[0][n-1] << endl;
}


Measured memory_bytes: 3052
n = int(input())
slist = [0]
for a in map(int, input().split()):
  slist.append(slist[-1] + a)
slist.append(slist[-1] + pow(10, 9) + 5)

prevs = None
c = 0
ans = 0
for s in sorted(slist):
  if prevs is None:
    prevs = s
    c = 1
  else:
    if prevs == s:
      c += 1
    else:
      ans += (c * (c - 1)) // 2
      c = 1
      prevs = s

print(ans)


Measured memory_bytes: 26724
public class Main {
	public static void main(String[] args){
		java.util.Scanner scan = new java.util.Scanner(System.in);
		String str1 = scan.nextLine();
		String str2 = scan.nextLine();

		str1 = str1 +str1;
		if(str1.indexOf(str2) != -1){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 26296
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int>pii;
vector<pii>comp(vector<pii>v)
{
	vector<int>za, zb;
	for (int i = 0; i < v.size(); i++)za.push_back(v[i].first), zb.push_back(v[i].second);
	sort(za.begin(), za.end());
	sort(zb.begin(), zb.end());
	for (int i = 0; i < v.size(); i++)
	{
		v[i].first = (lower_bound(za.begin(), za.end(), v[i].first) - za.begin()) * 2;
		v[i].second = (lower_bound(zb.begin(), zb.end(), v[i].second) - zb.begin()) * 2;
	}
	return v;
}
vector<pii>calc(vector<int>v)
{
	if (v.size() == 4)
	{
		vector<pii>r;
		r.push_back(make_pair(0, 0));
		r.push_back(make_pair(2, 0));
		r.push_back(make_pair(2, 2));
		r.push_back(make_pair(0, 2));
		return r;
	}
	int rr = 0;
	for (int i = 0; i < v.size() - 1; i++)
	{
		if (v[i] != v[i + 1])
		{
			rr = i;
			break;
		}
	}
	vector<int>z;
	for (int i = 0; i < rr; i++)z.push_back(v[i]);
	for (int i = rr + 2; i < v.size(); i++)z.push_back(v[i]);
	vector<pii>now = calc(z);
	vector<pii>ans;
	for (int i = 0; i < rr; i++)ans.push_back(now[i]);
	pii s = now[(rr + now.size() - 1) % now.size()], t = now[rr % now.size()];
	pii a = make_pair((s.first + t.first) / 2, (s.second + t.second) / 2), b = a;
	if (s.first == t.first)
	{
		if ((s.second < t.second) == (v[rr] == 1))b.first--, t.first--;
		else b.first++, t.first++;
	}
	else
	{
		if ((s.first < t.first) == (v[rr] == 1))b.second++, t.second++;
		else b.second--, t.second--;
	}
	ans.push_back(a);
	ans.push_back(b);
	for (int i = rr; i < now.size(); i++)ans.push_back(now[i]);
	ans[(rr + 2) % ans.size()] = t;
	//for (int i = 0; i < v.size(); i++)printf("%d ", v[i]); printf("\n");
	//for (int i = 0; i < ans.size(); i++)printf("%d %d   ", ans[i].first, ans[i].second); printf("\n");
	return comp(ans);
}
int main()
{
	int num;
	scanf("%d", &num);
	vector<int>v;
	int s = 0;
	for (int i = 0; i < num; i++)
	{
		int z;
		scanf("%d", &z);
		v.push_back((180 - z) / 90);
		s += v[i];
	}
	if (s != 4)
	{
		printf("-1\n");
		return 0;
	}
	vector<pii>r = calc(v);
	for (int i = 0; i < num; i++)printf("%d %d\n", r[i].first, r[i].second);
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,a,b) for(int i=(int)(a-1);i>=b;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define INF INT_MAX/3

int main(){
    cin.sync_with_stdio(false);
    string s;
    cin >> s;
    s[3] = '8';
    cout << s << endl;
    return 0;
}

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

int main()
{
  char string[81];
  int i;

  while(fgets(string, 81, stdin) != NULL)
    {
      while(strstr(string, "the") == NULL &&
	    strstr(string, "this") == NULL &&
	    strstr(string, "that") == NULL )
	{
	  for(i = 0; string[i] != '\0'; i++)
	    {
	      if(string[i] > 'z' || string[i] < 'a')
		continue;
	      string[i]++;
	      if(string[i] > 'z')
		string[i] = string[i] - 'z' + 'a' - 1;
	    }
	}
      printf("%s", string);
    }


  return 0;
}

      

Measured memory_bytes: 524
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

const int MAXN = 105;


bool can(const string &name, const string &kanban) {
  for(int i = 0; i < kanban.size(); ++i) {
    if(kanban[i] != name[0]) continue;
    for(int j = 1; i+j*(name.size()-1) < kanban.size(); ++j) {
      bool flag = true;
      for(int k = i, m = 0; m < name.size(); k += j, ++m) {
        if(kanban[k] != name[m]) {
          flag = false;
          break;
        }
      }
      if(flag) return true;
    }
  }
  return false;
}

int main() {
  int N;
  string name;
  while(cin >> N) {
    cin >> name;
    int res = 0;
    for(int i = 0; i < N; ++i) {
      string kanban;
      cin >> kanban;
      if(can(name, kanban)) {
        res += 1;
      }
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
#include <queue>
#include <deque>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N;
  cin>>N;
  vector<int>A(N);
  multiset<int>B;
  REP(i,N)cin>>A[i];
  B.insert(A[0]);
  FOR(i,1,N){
    auto it = B.lower_bound(A[i]);
    if(it==B.begin()){
      B.insert(A[i]);
    }else{
      B.erase(--it);
      B.insert(A[i]);
    }
  }
  cout<<B.size()<<endl;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> vec(n);
    for(int i=0;i<n;i++) cin >> vec[i];
    int ans=10000000;
    for(int i=1;i<=100;i++){
        int tmp=0;
        for(int j=0;j<n;j++){
            tmp+=(vec[j]-i)*(vec[j]-i);
        }
        ans=min(ans,tmp);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


ll dp[111][202020];
int main(){
    int n,w;
    cin>>n>>w;
    int a[n],b[n];
    rep(i,n)cin>>a[i]>>b[i];
    rep(i,n)rep(j,w){
        dp[i+1][j+a[i]]=max(dp[i+1][j+a[i]],dp[i][j]+b[i]);
        dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
    }
    ll ans=0;

    rep(i,w)ans=max(ans,dp[n][i+1]);
    cout<<ans<<endl;
    return 0;
}

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

int GCD[300][300]; 

int gcd(const int& lhs, const int& rhs){
    return (lhs % rhs == 0) ? rhs : gcd(rhs, (lhs%rhs));
}


int main(){
    int K,a,b,c;
    cin >> K;

    for(int i=0;i<300;++i){
        for(int j=0;j<300;++j){
            GCD[i][j] = -1;
        }
    }

    long long ans(0);
    int tmp,tmp2;
    
    for(a=1;a<=K;++a){
        for(b=1;b<=K;++b){
            for(c=1;c<=K;++c){
                if(GCD[a][b] == -1){
                    tmp = gcd(a,b);
                    GCD[a][b] = tmp;
                }else{
                    tmp = GCD[a][b];
                }

                if(GCD[tmp][c] == -1){
                    tmp2 = gcd(tmp,c);
                    GCD[tmp][c] = tmp2;
                }else{
                    tmp2 = GCD[tmp][c];
                }

                ans += tmp2;
            }
        }
    }

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


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

i64 N, K;

int main() {
  cin >> N >> K;

  i64 cnt = 0;
  while (1) {
    if (N < K) {
      cnt++;
      break;
    }
    N /= K;
    cnt++;
  }
  cout << cnt << endl;

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int i,j,k;
  long N,M;
  
  scanf("%ld %ld",&N,&M);
  
  if(N==1 && M ==1){
    puts("1");
    return 0;
  }
  else if(N == 1 || M == 1){
    printf("%ld\n",(N*M) -2);
    return 0;
  }
  else{
    printf("%ld\n",((N-2)*(M-2)));
    return 0;
  }
  return 0;
}


Measured memory_bytes: 128
N=int(input())
k=2
ans=1
factors=[]
i=1
while i*i<N-1:
  if (N-1)%i==0:
    ans+=1
  i+=1
while k*k<=N:
  n=0
  while pow(k,n)<=N:
    if (N-pow(k,n))%(pow(k,n+1))==0:
      ans+=1
      break
    n+=1
  k+=1
print(ans)

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

using namespace std;

#define gc getchar_unlocked
#define foi(i,n) for(int i=0;i<n;i++)
#define Foi(i,k,n) for(int i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define fol(i,n) for(ll i=0;i<n;i++)
#define Fol(i,k,n) for(ll i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)   scanf("%d",&x)
#define sl(x)   scanf("%lld",&x)
#define ss(s)   scanf("%s",s)
#define pi(x)   printf("%d\n",x)
#define pl(x)   printf("%lld\n",x)
#define ps(s)   printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pl;
typedef vector<int>     vi;
typedef vector<ll>      vl;
typedef vector<pii>     vpii;
typedef vector<pl>      vpl;
typedef vector<vi>      vvi;
typedef vector<vl>      vvl;
int mpow(int base, int exp); 
void ipgraph(int m);
void dfs(int u, int par);
const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vi g[N];
int a[N];

int mpow(int base, int exp) {
    base %= mod;
    int result = 1;
    while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
    }
    return result;
}

void ipgraph(int n, int m){
    int i, u, v;
    while(m--){
        cin>>u>>v;
        g[u-1].pb(v-1);
        g[v-1].pb(u-1);
    }
}

void dfs(int u, int par){
    for(int v:g[u]){
        if (v == par) continue;
        dfs(v, u);
    }
}


int main() {
    char a;
    cin>>a;
    if('A'<=a&&a<='Z')
        cout<<"A";
    else
    {
        cout<<"a";
    }
       
    return 0;
}

Measured memory_bytes: 10672
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int a,b,c,k; cin >> a >> b >> c >> k;
  int ans = 0, cnt = 0;
  if (k>=a) { ans += a; k -= a; }
  else { cout << k << endl; return 0; }
  k -= b;
  if (k>0) ans -= k;
  cout << ans << endl; return 0;
}

Measured memory_bytes: 3556
#include <stdio.h>

void	ft_sort(int *tab, int n)
{
	int tmp;
	int i;
	int j;
	i = 0;
	while (i < n - 1)
	{
		j = i + 1;
		while (j < n)
		{
			if (tab[i] < tab[j])
			{
				tmp = tab[i];
				tab[i] = tab[j];
				tab[j] = tmp;
			}
			j++;
		}
		i++;
	}
}


int main(void)
{
	int n, m;
	long total = 0;

	scanf("%d%d", &n, &m);
	int a[n];
	int i = 0;
	while (i < n)
	{
		scanf("%d", &a[i]);
		i++;
	}
	i = 0;
	while (i < n)
	{
		total += a[i];
		i++;
	}
	ft_sort(a, n);
	i = 0;
	int x,y;
	while (i < m)
	{
		if ((float)a[i] / total >= (float)1 / (4 * m))
			i++;
		else
			break ;
	}
	if (i == m)
		printf("Yes");
	else
		printf("No");
	return (0);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;
typedef int64_t ll;

int main() {
    string S;
    cin >> S;
    if (S == "ABC"){
        cout << "ARC" << endl;
    }
    else {
        cout << "ABC" << endl;
    }
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;



int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int a;
    cin >> a;
    cout << a + a * a + a * a * a;
    

    return 0;
}



Measured memory_bytes: 3636
#include "bits/stdc++.h"
#define rep(i, j) for (long long i = j; i > 0; i--)
using namespace std;

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

	vector<double> p(n);
	for (int i = 0; i < n; i++)
		cin >> p[i];

	vector<double> db(1001);
	vector<double> db_w(1001);
	vector<double> ruisekiwa(n + 1);

	db[1] = 1;
	db_w[1] = 1;
	for (int i = 2; i <= 1000; i++) {
		db[i] = db[i - 1] + i;
		db_w[i] = db[i] / i;
	}

	ruisekiwa[0] = 0;
	for (int i = 1; i <= n; i++) {
		ruisekiwa[i] = db_w[p[i - 1]] + ruisekiwa[i - 1];
	}

	double ans = 0;

	for (int i = k; i <= n; i++) {
		double num = ruisekiwa[i] - ruisekiwa[i - k];
		if (num > ans)
			ans = num;
	}


	printf("%f", ans);

	return 0;
}

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

using ll = long long;
#define ff first
#define ss second

void solve()
{
	int n;
	cin>>n;
	int a[111];
a[0] = 0;
	for (int i = 1; i <= n; i++)
		cin>>a[i];
	for (int i = 1; i <= n; i++)
	{
		a[i] += a[i - 1];
	}
	int ans = 1e9;
	for (int i = 1; i <= n; i++)
	{
		int dif = abs(a[i] - (a[n] - a[i]));
		ans = min(ans, dif);
	}
	cout<<ans<<endl;
}

int main()
{
	int t = 1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
}


Measured memory_bytes: 256
import bisect

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

z = [0 for i in range(n)]
r = [0 for i in range(n)]

s = []
for i in range(len(a)):
    idx = bisect.bisect_left(s,a[len(a)-1-i])
    r[len(a)-1-i] = idx
    s.insert(idx,a[len(a)-1-i])
for i in range(n):
    z[i] = bisect.bisect_left(s,a[i])

l = [0 for i in range(n)]
ans = 0
for i in range(n):
    ans += r[i] * k * (k+1) // 2
    l[i] = z[i] - r[i]
    ans += l[i] * k * (k-1) // 2
print(ans%(10**9+7))

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

int main(){
	int h,w;
	cin >> h >> w;
	while(h!=0 || w!=0){

		for(int j=0;j<w;j++){
			cout << "#";
		}
		cout << endl;

		for(int i=1;i<h-1;i++){
			cout << "#";
			for(int j=1;j<w-1;j++){
				cout << ".";
			}
			cout << "#" << endl;
		}

		for(int j=0;j<w;j++){
			cout << "#";
		}
		cout << endl;

		cout << endl;
		
		cin >> h >> w;
	}
}

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

int main() {
  int n;
  cin >> n;
  long long ans = 0;
  long long bef = -1;
  for ( int i = 0; i < n; i++ ) {
    long long a;
    cin >> a;
    if ( bef > a ) {
      ans += (bef-a);
    } else {
      bef = a;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3628
import sys
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
n,k,s=map(int,input().split())
a=10**9
# half1=s//2
# half2=(s+1)//2
li=[]
if s==10**9:
    for i in range(n):
        if i<k:
            li.append(s)
        else:
            li.append(1)
    print(*li)
    quit()

for i in range(n):
    if i<k:
        li.append(s)
    else:
        li.append(a)
print(*li)

Measured memory_bytes: 49392
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    int n;
    string s;
    cin >> n >> s;
    int l = 0;
    int cnt = 0;
    for(char c: s) {
        if (c == '(')
            cnt += 1;
        else
            cnt -= 1;
        if (cnt < 0) {
            cnt = 0;
            l += 1;
        }
    }
    string ans;
    while(l--)
        ans += "(";
    ans += s;
    while(cnt--)
        ans += ")";
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 256
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define int long long
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

int a[N],sum[N],siz[N],ans[N],n;
vector<int>e[N];

void dfs1(int u,int fa) {
	siz[u]=1;
	for(auto v:e[u]) {
		if(v==fa) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
	}
}

void dfs2(int u,int fa) {
	ans[a[u]]+=siz[u]*(n-siz[u]-sum[a[u]]+1);
	sum[a[u]]+=siz[u];
	int ss=sum[a[u]];
	int pre=0;
	for(auto v:e[u]) {
		if(v==fa) continue;
		sum[a[u]]=n-siz[v];
		dfs2(v,u);
		ans[a[u]]+=pre*siz[v];
		pre+=siz[v];
	}
	sum[a[u]]=ss;
}

signed main() {
	IOS;
#ifdef xiaofan
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
#endif

	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<n; i++) {
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1,1);
	dfs2(1,1);
	for(int i=1; i<=n; i++) cout<<ans[i]<<endl;





	return 0;
}



Measured memory_bytes: 55188
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <bitset>
#include <set>
#include <iomanip>
#include <functional>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
//'A' = 65, 'a' = 97

int main()
{
    int n, k;
    cin >> n >> k;
    int h[n];
    rep(i, 0, n) {
        cin >> h[i];
    }

    sort(h, h + n);

    int ans = 1e9;
    for (int i = 0; i <= n - k; i++) {
        ans = min(ans, h[i + k - 1] - h[i]);
    }

    cout << ans << endl;

}


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

int main(){
  int N;
  cin>>N;
  char c[N];
  bool flag=false;
  for(int i=0;i<N;i++){
    cin>>c[i];
    if(c[i]=='Y') flag=true;
  }
  if(flag) cout<<"Four"<<endl;
  else cout<<"Three"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reprl(i, n) for(ll i = n; i >= 0; i--)
#define fori(i, m, n) for(int i = m; i < (int)n; i++)
#define forl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define all(v) v.begin(), v.end()
ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}
const string btos(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  int a,b;cin>>a>>b;
  int ans=(a+b+1)/2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
arr = []
  
for i in range(5):
    x = int(input())
    arr.insert(i, x)

k = int(input())
flag = 0
for i in range(5):
    for j in range(5):
        if abs(arr[i]-arr[j]) > k:
            flag = 1
            break

if flag == 1:
    print(':(')
else:
    print('Yay!')

Measured memory_bytes: 3060
#include<iostream>
#include<map>
#include<cassert>
using namespace std;

int N;

int main() {
  cin >> N;
  map<int, int> M;
  for (int k = 1; k <= N; k++) {
    int k2 = k;
    for (int d = 2; d <= k2; d++) {
      while (k2 % d == 0) {
        k2 /= d;
        M[d]++;
      }
    }
    assert(k2==1);
  }
  int c2 = 0, c4 = 0, c14 = 0, c24 = 0, c74 = 0;
  for (pair<int, int> exp : M) {
    if (exp.second >= 2) c2++;
    if (exp.second >= 4) c4++;
    if (exp.second >= 14) c14++;
    if (exp.second >= 24) c24++;
    if (exp.second >= 74) c74++;
  }
  int cnt = 0;
  cnt += (c2-c4) * c4 * (c4-1) / 2 + c4 * (c4-1) * (c4-2) / 2; // 75=3*5*5
  cnt += (c4-c14) * c14 + c14 * (c14-1); // 75=5*15
  cnt += (c2-c24) * c24 + c24 * (c24-1); // 75=3*25
  cnt += c74; // 75=75;
  cout<<cnt<<endl;
}

Measured memory_bytes: 3592