akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
 
// Remove GCC optimizer for codechef
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
using namespace __gnu_pbds;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define endl "\n"
#define int long long
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
const int INF = 2e9;
const double PI = acos(-1);
const int N = 1e6 + 7;
int mod = 998244353;

int dp[N], h[N], n, k;

int solve(int x)
{
    if(x == n)
        return 0;
    if(dp[x] != -1)
        return dp[x];
    int &res = dp[x];
    res = solve(x + 1) + abs(h[x+1] - h[x]);
    for(int i = 2; x + i <= n && i <= k; i++)
        res = min(res, solve(x + i) + abs(h[x+i] - h[x]));
    return res;
}

int32_t main()
{
    IOS;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> h[i];
    memset(dp, -1, sizeof(dp));
    cout << solve(1) << endl;
    return 0;
}

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

#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;
const long long INF=1e18;
typedef pair<ll,ll> pll;
#define F first
#define S second



signed main(){
  string a,b;
  cin>>a>>b;
  vector<pll> A(a.size()+2,{INF,INF}),B(b.size()+2,{INF,INF});
  ll mi0=INF;
  ll mi1=INF;
  for(ll i=a.size()-1;i>=0;i--){
    A[i+1]={mi0,mi1};
    if(a[i]=='0'){mi0=i+1;}
    else{mi1=i+1;}
  }
  
  A[0]={mi0,mi1};
  mi0=INF;
  mi1=INF;
  for(ll i=b.size()-1;i>=0;i--){
    B[i+1]={mi0,mi1};
    if(b[i]=='0'){mi0=i+1;}
    else{mi1=i+1;}
  }
  B[0]={mi0,mi1};
  vector<vector<pll>> dp(a.size()+2,vector<pll>(b.size()+2,{INF,-1}));
  for(ll i=a.size()+1;i>=0;i--){
    for(ll t=b.size()+1;t>=0;t--){
      if(A[i].F==INF && B[t].F==INF){dp[i][t]={1,0};}
      else if(A[i].S==INF && B[t].S==INF){dp[i][t]={1,1};}
      else{
	dp[i][t].F=dp[(A[i].F==INF?(ll)a.size()+(ll)1:A[i].F)][(B[t].F==INF?(ll)b.size()+(ll)1:B[t].F)].F+1;
	dp[i][t].S=0;
	if(dp[i][t].F>dp[(A[i].S==INF?(ll)a.size()+1:A[i].S)][(B[t].S==INF?(ll)b.size()+1:B[t].S)].F+1){
	  dp[i][t].F=(dp[A[i].S==INF?(ll)a.size()+1:A[i].S][B[t].S==INF?(ll)b.size()+1:B[t].S].F+1);
	  dp[i][t].S=1;
	}
      }
    }
  }
  
  ll wx=0,wy=0;
  while(wx!=a.size()+1 || wy!=b.size()+1){
    cout<<dp[wx][wy].S;
    if(dp[wx][wy].S==0){
      wx=(A[wx].F==INF?(ll)a.size()+1:A[wx].F);
      wy=(B[wy].F==INF?(ll)b.size()+1:B[wy].F);
    }
    else{
      wx=(A[wx].S==INF?(ll)a.size()+1:A[wx].S);
      wy=(B[wy].S==INF?(ll)b.size()+1:B[wy].S);
    }
  }
  cout<<endl;
  
  
  return 0;
}



Measured memory_bytes: 253324
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <istream>
#include <map>
#include <set>
#include <queue>
#define rep0(i,n) for (int i = 0; i <= (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define REP(a,b) for (int i = a; i <= (b); ++i) 
#define mREP(a,b) for (int i = a; i == (b); --i)
#define mod 1e9 + 7
typedef long long ll;
using namespace std;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	/*
	　　　　　 　 _... ..._
	　　　　　 , ´⌒ ⌒ヽ
	　　　 　 ﾉｨ（ノﾉ）ﾉ）ﾉ）
	　　　 　 （（q|.ﾟ ヮﾟﾉ|ﾊ
	　　　　　　△ﾑ,8ﾑﾌつ
	　　　　　/(ﾝ_/＿ヽ＼
	　　　　 ～～i_ﾌ_ﾌ～´
	*/
	int n, m;
	string s;
	cin >> n >> s >> m;

	rep0(i, n - 1) {
		if (s[i] != s[m - 1]) {
			s[i] = '*';
		}
	}
	cout << s << endl;
	return 0;
}


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

const int MOD=998244353;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int a[200],b[200];
int main(){
	int n;cin>>n;
	rep(i,n){
		cin>>a[i]>>b[i];
	}
	rep(i,n-2){
		bool ok=true;
		rep(j,3){
			if(a[i+j]!=b[i+j])ok=false;
		}
		if(ok){puts("Yes");return 0;}
	}
	puts("No");
}

Measured memory_bytes: 3628
#include <iostream>

using namespace std;


void insertion_sort(int *seq, int length) {
  int key, j;
  for (int i = 1; i < length; i ++) {
    key = seq[i];
    j = i - 1;
    while (j >= 0 && seq[j] > key) {
      seq[j + 1] = seq[j];
      j --;
    }
    seq[j + 1] = key;
  }
}


int main() {
  int n, q;
  int S[10000], T[500];
  int count;

  cin >> n;
  for (int i = 0; i < n; i ++) {
    cin >> S[i];
  }
  cin >> q;
  for (int i = 0; i < q; i ++) {
    cin >> T[i];
  }
  insertion_sort(S, n);
  insertion_sort(T, q);

  for (int i = 0, j = 0; i < q && j < n; i ++) {
    if (i != 0 && T[i] == T[i-1]) continue;
    while (T[i] >= S[j]) {
      if (T[i] == S[j]) {
        count += 1;
        j++;
        break;
      }
      j++;
    }

  }
  cout << count << endl;

  return 0;
}



Measured memory_bytes: 3088
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
template<typename T>
T minch(T& l, T r) {
    return l = min(l, r);
}
template<typename T>
T maxch(T& l, T r) {
    return l = max(l, r);
}
template<typename T>
void output(const T& val) {
    cout << val << endl;
}
template<typename T>
void output(const vector<T>& vec, const bool newline = false) {
    for (const T& val : vec)cout << val << (newline ? '\n' : ' '); cout << endl;
}
template<typename T>
void output(const vector<vector<T>>& mat) {
    for (const auto& row : mat)output(row);
}
// ============ template finished ============

int main()
{
    int K, A, B;
    cin >> K >> A >> B;
    REP(i, A, B + 1) {
        if (i%K == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
    return 0;
}


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

int main() {
  vector<int>a(32);
  a={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int n;
  cin>>n;
  n--;
  cout<<a[n]<<endl;
  
  
}

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

# define fori(i,n)          for(int i=0;i<n;i++)
# define forl(i,n)          for (ll i=0;i<n;i++)
# define pb                 push_back
# define mp                 make_pair
# define X                  first
# define Y                  second
# define all(v)             v.begin(),v.end()
# define in_ar_int(arr,n)   int arr[n]; fori(i,n) cin >> arr[i];
# define in_ar_ll(arr,n)    ll arr[n]; fori(i,n) cin >> arr[i];
# define endl               "\n"
# define R0                 return 0
# define mod                1000000007
# define pi                 3.1415926536


typedef long long ll;
typedef string str;

 
ll power (ll a, ll b){
    ll ans=1;
    while(b){
		if (b & 1) ans*=a;
		a*=a;
		b/=2;
    }
    return ans;
}

ll kadane(ll a[], int size) 
{ 
    ll max_so_far = INT_MIN, max_ending_here = 0; 
  
    for (int i = 0; i < size; i++) 
    { 
        max_ending_here = max_ending_here + a[i]; 
        if (max_so_far < max_ending_here) 
            max_so_far = max_ending_here; 
  
        if (max_ending_here < 0) 
            max_ending_here = 0; 
    } 
    return max_so_far; 
} 

bool isprime(int n) { 
    if (n <= 1) return false; 
    if (n <= 3) return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
    for (int i=5; i*i<=n; i=i+6){
		if (n%i == 0 || n%(i+2) == 0) 
		return false; 
	}
    return true; 
} 

long long nCr(int n,int r){
    if(n==r) return 1;
    else if (r==0) return 1;
    else return nCr(n-1,r-1)+nCr(n-1,r);
}

int sdigit(int x){
    int ans=0;
    while(x){
		ans+=x%10;
		x/=10;
    }
    return ans;
}

int bs(int a[],int b,int l,int r){
    int mid=l + (r-l)/2;
    if(l>r) return -1;
    if(a[mid]==b||l==r)	return mid;
    if(a[mid]>b)	return bs(a,b,l,mid-1);
    else return bs(a,b,mid+1,r);
}

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

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int chill=1;
    // cin >> chill;
    while(chill--){
	solve();
    }
}



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

# define C continue;
# define R return

# define D double
# define I insert
# define ll long long
# define ld long double

# define ull unsigned long long
# define ui unsigned int

# define pb push_back
# define pf push_front

# define vi vector < int >
# define vc vector < char >
# define vs vector < string >
# define vb vector < bool >
# define vd vector < D >
# define vll vector < ll >
# define vull vector < ull >
# define vld vector < ld >
# define PQ priority_queue

# define vvi vector < vector < int > >
# define vvb vector < vector < bool > >
# define vvc vector < vector < char > >
# define vvs vector < vs >
# define vvll vector < vector < ll > >
# define vvd vector < vector < D > >
# define vvld vector < vector < ld > >

# define all(v) (v).begin() , (v).end()
# define allrev(v) (v).rbegin() , (v).rend()
# define allcomp(v) v.begin() , v.end() , comp
# define allrevcomp(v) v.rbegin() , v.rend() , comp

# define pii pair < int , int >
# define pll pair < ll , ll >
# define pld pair < ld , ld >
# define pDD pair < D , D >

# define vpld vector < pld >
# define vpii vector < pii >
# define vpll vector < pll >
# define vpDD vector < pDD >

# define vvpii vector < vector < pii > >
# define F first
# define S second
# define mp make_pair

# define dist(a,b,p,q) sqrt((p-a)*(p-a) + (q-b)*(q-b))

# define pp(n) printf("%.10Lf",n);
# define line cout<<"\n";
# define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);

string vow = "aeiou";
int month[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};

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

const ld pie = 3.1415926535897932384626 ;
const ll mod = 1e9 + 7 ;

/// Tip : If a and b are positive integers ; we may say - ceil (a/b) = 1 + floor ( (a-1)/b ) .

void solve ( int test_case )
{
    int n ;
    cin >> n ;

    vi v ( n + 1 ) ;
    for ( int i = 1 ; i <= n ; i ++ )
        cin >> v[i] ;

    int ans = 0 ;

    for ( int i = 1 ; i <= n ; i += 2 )
    {
        if ( v[i] % 2 )
            ans ++ ;
    }

    cout << ans ; line ;

}

int main()
{
    int t = 1;
    // cin >> t;

    for ( int i = 1 ; i <= t ; i ++ )
    {
        solve ( i ) ;
    }

    return 0;
}


Measured memory_bytes: 3628
from bisect import bisect_left

class SegTree:
    def __init__(self, raw_data):
        n = len(raw_data)
        self.size = 1 << (n.bit_length()) # 葉の要素数
        self.data = [0] * (2*self.size)
        self.build(raw_data)

    def build(self, raw_data):
        for i, x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1, 0, -1):
            x = self.data[2*i]
            y = self.data[2*i+1]
            self.data[i] = x if x > y else y # ここを変更
    
    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[2*i]
            y = self.data[2*i+1]
            self.data[i] = x if x > y else y # ここを変更
            i >>= 1
    
    def get_data(self, i):
        return self.data[i+self.size]
    
    # これを変更
    def get_max(self, L, R):
        L += self.size
        R += self.size + 1
        x = 0
        while L < R:
            if L & 1:
                y = self.data[L]
                if x < y: x = y
                L += 1
            if R & 1:
                R -= 1
                y = self.data[R]
                if x < y: x = y
            L >>= 1
            R >>= 1
        return x

N = int(input())
robots = sorted([tuple(map(int, input().split())) for _ in range(N)])
X, D = zip(*robots)
mod = 998244353

affects = [0] + [bisect_left(X, x+d) for x, d in robots]
seg = SegTree(affects)

S = [0] * len(affects)
for n in range(N, 0, -1):
    affect = affects[n]
    x = seg.get_max(n, affect)
    S[n] = x
    seg.update(n, x)

dp = [0] * (N+1)
dp[0] = 1
dp_cum = [1] * (N+1)
for n, r in enumerate(S[1:], 1):
    dp[r] += dp_cum[n-1]
    dp[r] %= mod
    dp_cum[n] = dp_cum[n-1] + dp[n]
    dp_cum[n] %= mod
print(dp_cum[-1])



Measured memory_bytes: 147368
#define rep(i, n) for (int i = 0; i < (n); i++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MOD = 1000000007;
// MAX int 2,147,483,647
// MAX O(n) 10^

vector<int> D;

bool isValid(int x) {
    while(x > 0) {
        if (find(D.begin(), D.end(), x % 10) != D.end()) return false;
        x /= 10;
    }
    return true;
}

int main() {
    int N, K;
    cin >> N >> K;
    int tmp;
    rep(i, K) {
        cin >> tmp;
        D.push_back(tmp);
    }

    int ans;
    for (int i = N; i < 1000000; i++) { // 100000 * 5 * 10 -> OK
        if (isValid(i)) {
            ans = i;
            break;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define endl '\n'
int main(){
    ll n;
    cin>>n;
    ll c=1;
    for(ll i=2;i*i<=n;i++){
        ll j=i;
        ll x=n;
        while(x%j==0)x/=j;
        if(x==1 || x%j==1)c++;
    }
    ll y=sqrt(n);
    for(ll i=1;i*i<=(n-1);i++){
        ll x=n-1;
        if(x%i==0){
            ll p=x/i;
            ll q=i;
            if(p==q && p>y)c++;
            else{
                if(p>y)c++;
                if(q>y)c++;
            }
        }
    }
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pi 3.1415926535897
#define io  ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;
int main(){
    int d;
    double de;
    cin>>d;
    de=2*pi*d;
   printf("%.6lf\n",de);

return 0;
}


Measured memory_bytes: 3760
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int s = scanner.nextInt();
        int[] num = new int[n + 1];
        int max = Integer.MIN_VALUE;
        int top = 0;
        for (int i = 0; i < s; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            num[a] += b;
            if (top == a && b < 0) {
                max = Integer.MIN_VALUE;
                for (int j = 1; j <= n; j++) {
                    if (max < num[j]) {
                        top = j;
                        max = num[j];
                    }
                }
            } else if (top != a && b > 0) {
                if (num[top] < num[a]) {
                    top = a;
                    max = num[a];
                } else if (num[top] == num[a]) {
                    if (top > a) {
                        top = a;
                    }
                }
            }
 
            System.out.println(top + " " + num[top]);
        }
    }
}


Measured memory_bytes: 108712
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

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



int main(void){

	int a,b,h;
	cin >> a >> b >> h;

	printf("%d\n", (a+b)*h/2);


	return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector> // vectorを使うためにインクルードする
using namespace std;
 
int main() {
	char a[50];
	scanf("%4s", a); 
	if (a[0] == a[1] || a[1] == a[2] || a[2] == a[3]) {
		cout << "Bad" << endl;
	}
	else {
		cout << "Good" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
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 T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    ll N, T;
    cin >> N >> T;
    vll t(N + 1);
    ll ans = 0, time = 0;
    for (size_t i = 0; i < N; i++)
    {
        cin >> t[i];
    }
    t.back() = INF;
    for (size_t i = 0; i < N; i++)
    {
        ans += min(T, t[i + 1] - t[i]);
    }

    cout << ans;
    return 0;
}

Measured memory_bytes: 1792
"""
CでAやBが0.5枚できる分だけ買う意味はないので、必ず一枚作れるように買う
X,Yが 10**5までなので、Cで何枚作るか決めて、残りをA、B単品で埋めた時のコストの最小値を全探索
"""

A,B,C,X,Y  = map(int, input().split())


ans = float("inf")
# iはCで何枚のA,Bを作るか
for i in range(max(X,Y)+1):
    # C買う分のコスト
    cost = 2*i*C
    # 残りのAのコスト
    if i < X:
        cost += (X-i)*A
    # 残りのBのコスト
    if i < Y:
        cost += (Y-i)*B
    ans = min(ans, cost)

print(ans)

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

int main() {
    int n,m;
    int64_t x;
    cin >> n >> m >> x;
    vector<int64_t> c(n);
    vector<vector<int64_t>> a(n, vector<int64_t> (m));
    rep(i,n) {
        cin >> c[i];
        rep(j,m) cin >> a[i][j];
    }
    
    int64_t min_c = 100100100100100;
    for(int tmp=0;tmp < (1 << n) ;tmp++) {
        bitset<12> s(tmp);
        vector<int64_t> vec(m);
        int64_t sum_c = 0;
        rep(i,n){
            if(s.test(i)) {
                rep(j,m) vec[j] += a[i][j];
                sum_c += c[i];
            }
        }
        bool ok = true;
        for(auto v:vec) {
            if(v < x) ok = false;
        }
        if(ok) min_c = min(min_c,sum_c);
    }
    if(min_c != 100100100100100) cout << min_c << endl;
    else cout << "-1" << endl;

    return 0;
}

Measured memory_bytes: 3636
from heapq import heappush, heappop

inf = float('inf')
n = int(input())
g = []
for i in range(n):
    line = list(map(int, input().split()[2:]))
    g.append(zip(line[0::2], line[1::2]))

dist = [inf] * n
dist[0] = 0
heap = [(0, 0)]

while heap:
    current = heappop(heap)[1]
    for v, c in g[current]:
        new_dist = dist[current] + c
        if new_dist < dist[v]:
            dist[v] = new_dist
            heappush(heap, (new_dist, v))

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

Measured memory_bytes: 40424
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second

using namespace std;

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << endl;
  err(++it, args...);
}

int main(){
  long long A[3], K;
  for(int i = 0; i < 3; i++) cin >> A[i];
    cin >> K;

  long long ans = 0;
  if(K <= A[0]){
    cout << K << endl;
    return 0;
  }
  ans += A[0];
  K -= A[0];

  if(K <= A[1]){
    cout << ans << endl;
    return 0;
  }
  K -= A[1];

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

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
signed main(){
  int a;
  cin>>a;
  vector<string> b(a);
  fo(i,a)
  cin>>b.at(i);
  string e;
  vector<int> c(26,1000000000),d(26,0);
  vector<int> p=d;
  for(int i=0;i<a;i++){
    e=b.at(i);
    Sort(e);
    d=p;
    for(int j=0;j<e.size();j++){
      fo(k,26){
        if(e.at(j)-'a'==k){
          d.at(k)++;
          break;
        }
      }
    }
    fo(j,26)
      c.at(j)=min(c.at(j),d.at(j));
  }
  string s="";
  for(char i='a';i<='z';i+=0x1){
    fo(j,c.at(i-'a'))
    s+=i;
  }
  cout<<s<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 100000
void run();
int check(int data[], int len);

int main(int argc, char const *argv[]) {
  run();
  return 0;
}

void run(){
  char *input = (char*)malloc(sizeof(char) * MAXLEN);
  scanf("%s", input);
  int data[MAXLEN];
  int len = strlen(input);
  for(int i = 0; i < len; i++){
    if(input[i] == 'B') data[i] = 0;
    if(input[i] == 'W') data[i] = 1;
  }
  int count = 0;
  for(int i = 0; i < len - 1; i++){
    if(data[i] != data[i+1]) count++;
  }
  printf("%d\n", count);
}

int check(int data[], int len){
  int ini = data[0];
  for(int i = 1; i < len; i++){
    if(data[i] != ini){
      return 1;
    }
  }
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long 
signed main(){
  int n,k;
  cin>>n>>k;
  int k1=0,k2=0;
  for(int i=1;i<=n;i++){
    k1+=(i%k==0);
    k2+=(i%k==k/2);
  }
  cout<<k1*k1*k1+(k%2==0)*k2*k2*k2<<endl;
  return 0;
}


Measured memory_bytes: 256
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[w*[0]for _ in range(h)]
dp[0][0]=(1<<(80+(a[0][0]-b[0][0])))|(1<<(80+(b[0][0]-a[0][0])))
for i in range(h):
  for j in range(w):
    if i!=0:
      dp[i][j]|=dp[i-1][j]<<(80+(a[i][j]-b[i][j]))
      dp[i][j]|=dp[i-1][j]<<(80+(b[i][j]-a[i][j]))
    if j!=0:
      dp[i][j]|=dp[i][j-1]<<(80+(a[i][j]-b[i][j]))
      dp[i][j]|=dp[i][j-1]<<(80+(b[i][j]-a[i][j]))
ans=1<<50000
for i in range(50000):
  if dp[h-1][w-1]&(1<<i):ans=min(abs(i-(h+w-1)*80),ans)
print(ans)

Measured memory_bytes: 17012
#include<bits/stdc++.h>
using namespace std;
int main(){
long long a,b,x, r;
	scanf("%lld%lld%lld",&a,&b,&x);

	
			if(a==0)
			 r=(b/x)+1;
			 else
			 r=(b/x)-(a-1)/x;
			 printf("%lld",r);
			
			
	
}

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

int main()
{
	string S;

	cin >> S;

	int i = 0;

	int num = 0;

	int N = S.length();

	while (i < N/2 )
	{
		if (S[i] != S[(N-1) - i]) {
			S[N - i] = S[i];

			num++;
		}
		i++;
	}

	cout << num << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5;
int n , a[4][N], dp[N][4];
int calc(int i , int cnt ){
    if(i == n)
        return 0;
    int &ret = dp[i][cnt];
    if(ret != -1)
        return ret;
    for(int j = 1 ; j <= 3; j++){
        if(j == cnt)continue;
        ret = max(ret , a[j][i] + calc(i + 1, j));
    }
    return ret;
}
int main(){
    scanf("%d" , &n);
    for(int i = 0 ; i < n ; i++){
        scanf("%d%d%d" , &a[1][i] , &a[2][i] , &a[3][i]);
    }
    memset(dp , -1 , sizeof dp);
    printf("%d\n" , calc(0 , 0));
    return 0;
}

Measured memory_bytes: 20352
#include <iostream>
using namespace std;
int min_cost(int h[],int n,int k){
    int dp[n],minn=0;
    dp[0]=0,dp[1]=abs(h[0]-h[1]);
   for(int i=2;i<n;i++){
       dp[i]=dp[i-1]+abs(h[i]-h[i-1]);
       if(i-k >=0 ){
       for(int j=i-k;j<i;j++){
           minn=dp[j]+abs(h[j]-h[i]);
           if(minn < dp[i]) dp[i]=minn;
       }
       }
       else{
           for(int j=0;j<i;j++){
               minn=dp[j]+abs(h[j]-h[i]);
               if(minn < dp[i]) dp[i]=minn;
           }
       }
   }
    return dp[n-1];
}
int main() {
    int n,k;
    cin>>n>>k;
    int h[n];
    for(int i=0;i<n;i++) cin>>h[i];
    cout<<min_cost(h,n,k);
	return 0;
}

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

int main (){
    int N = 0;
    cin >> N;
    vector<int> A(N,0);
    int sum = 0;
    for(int i = 0; i < N; i++) {
    cin >> A.at(i);
    if (A.at(i)%2)
    {
        if (!(i%2))
        {
            sum++;
        }
        
    }
    
    }
    cout << sum << endl;


    
}

Measured memory_bytes: 3628
while true
    n = gets.to_i
    if n ==0
        break
    end
    num = Array.new(n)
    line = gets
    for i in 1..n do
        num = line.split.map(&:to_i)
    end
    print num[0]
    cont = false
    for i in 1..n-1 do
        if num[i] == num[i-1] + 1
            cont = true
            next
        end
        if cont
            print "-" + num[i-1].to_s + " " + num[i].to_s
        else
            print " " + num[i].to_s
        end
        cont = false
    end
    if cont
        print "-" + num[n-1].to_s
    end
    puts
end

Measured memory_bytes: 6120
import java.math.BigInteger

fun ac104(args: Array<String>) {
    val (N, K) = args[0].split(" ").map { it.toLong() }
    var ans :BigInteger = BigInteger.ZERO

    ans += (1..3).map { BigInteger.valueOf(N / K) }.reduce { acc, num -> acc * num }

    if (K % 2 == 0L) {
        val tmp = BigInteger.valueOf((1..N).filter { it % K == K/2 }.size.toLong())
        ans += (1..3).map { tmp }.reduce { acc, num -> acc * num }
    }

    println(ans)
}

fun main(args: Array<String>) {
    ac104(readLineList())
}

fun readLineList(): Array<String> {
    val lineList = mutableListOf<String>()
    while (true) {
        val line = readLine()
        if (line.isNullOrBlank()) {
            break
        } else {
            lineList.add(line!!)
        }
    }
    return lineList.toTypedArray()
}

Measured memory_bytes: 38716
# ＤＦＳ, パターン列挙_竹'n'本の使用パターン

n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]

stack = [[0],[1],[2],[-1]] # 初期化_ここでは竹の使用パターン4つを設置
ptns = [] # パターン候補の器_初期化
 
while stack: # stackが空になるまでループ
    tmp = stack.pop() # パターンの候補を pop
    if len(tmp) == n: # 条件に合えば append
        ptns.append(tmp)
    elif len(tmp) < n: # 条件に合わなければ...
        w = tmp + [0] # パターンの候補を作成して...
        x = tmp + [1] # 〃
        y = tmp + [2] # 〃
        z = tmp + [-1]
        stack += [w, x, y, z]  # 積む

ans = 10**9
for i in range(len(ptns)):
    if 0 not in ptns[i] or 1 not in ptns[i] or 2 not in ptns[i]:
        continue
    abc = [0, 0, 0, -30]
    for j in range(n):
        tmp = ptns[i][j]
        if tmp >= 0:
            abc[tmp] += l[j]
            abc[3] += 10
    mp = abc[3]
    mp += abs(abc[0] - a)
    mp += abs(abc[1] - b)
    mp += abs(abc[2] - c)
    ans = min(ans, mp)

print(ans)

'''
# パターン列挙と探索を並行して処理

n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]

stack = [[0],[1],[2],[-1]]

ans = 10**9
while stack:
    tmp = stack.pop()
    if len(tmp) == n:
        if 0 not in tmp or 1 not in tmp or 2 not in tmp:
            continue
        abc = [0, 0, 0, -30]
        for j in range(n):
            if tmp[j] >= 0:
                abc[tmp[j]] += l[j]
                abc[3] += 10
        mp = abc[3]
        mp += abs(abc[0] - a)
        mp += abs(abc[1] - b)
        mp += abs(abc[2] - c)
        ans = min(ans, mp)

    elif len(tmp) < n:
        w = tmp + [0]
        x = tmp + [1]
        y = tmp + [2]
        z = tmp + [-1]
        stack += [w, x, y, z]

print(ans)
'''

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;

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

const int limit=100010;
bool red[limit];
int num[limit];

int main(void){
	int n,m;
	cin >> n >> m;

	red[0]=true;
	rep(i,n) num[i]=1;

	rep(i,m){
		int x,y;
		cin >> x >> y;
		x--,y--;
		num[x]--,num[y]++;
		if(red[x]) red[y]=true;
		if(num[x]==0) red[x]=false;
	}

	int ans=0;
	rep(i,n) if(red[i]&&num[i]>0) ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 768
import sys
import os

N,K = map(int,input().split())


count=[0]*N

KK=K
i=0
while  KK >= 1:
    i=i+1
    for j in range(int(KK)):
        if j<N and (j+1)!=KK:
            count[j]=count[j]+1
        #print(j)
    KK=KK/2

sum=0
for l in range(N):
    sum=sum + (1/N)*(1/2)**(count[l])


print(sum)

Measured memory_bytes: 3828
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<map>
#include<cstdint>
#include<unordered_map>
#include<boost/multiprecision/cpp_int.hpp>


#define rep(i, n) for(int i = 0; i < ( int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second

namespace mp = boost::multiprecision;

using cpp_int = mp::cpp_int;
using ll = long long;
using uint1024_t = mp::uint1024_t;
using namespace std;


int main() {
	int n;
	scanf("%d",&n);
	int ans = 0;
	rep(i, n) {
		int a;
		scanf("%d",& a);
		ans += a - 1;
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 256
#108c
import math
N,K = map(int, input().split())

#a,b,cが全て
# = K/2*(2n+1) …(1) 0 <= n , K/2*(2n+1) <= N
# = K*n  　　　…(2) 0 < n  , K*n <=N
#ならOK。ただし、a,b,cは整数なのでK/2が整数でなければ(1)はNG

if K == 1:
    #すべてのa,b,cがOK
    print(pow(N,3))
else:
    #(2)はKに関わらずOK
    #K*n <= N
    #n <= N/K
    #print("(2)K*n")
    #print([i*K for i in range(1,1+int(N/K))])
    ans = pow(int(N/K),3)
    
    if K%2 == 0:
        #(1)も考えてやる
        #K/2*(2n+1) <= N
        #K*(2n+1) <= 2N
        #2n+1 <= 2N/K
        #2n <= 2N/K - 1
        #n <= N/K - 1/2
        n_limit = int(N/K - 1/2)
        #print("(1)K/2*(2n+1)")
        if K/2 <= N:
            #print([int((K/2)*(1+(2*i))) for i in range(0,n_limit + 1)])
            ans += pow(n_limit + 1,3) #n = 0の時もOKなので+1
    
    print(ans)

Measured memory_bytes: 3060
while(1):
    size=sorted([int(x) for x in raw_input().split()])
    if size[0]==0:
        break
    else:
        cr=size[0]**2+size[1]**2
        n=int(raw_input())
        for i in range(n):
            r=int(raw_input())
            if 4*r**2>cr:
                print 'OK'
            else:
                print 'NA'

Measured memory_bytes: 4212
#include <bits/stdc++.h>
#include <iostream>
#include <tuple>
#include <string>
using namespace std;
int main(void){
    std::vector<tuple<string,int,int>> book;
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        string tmpS;
        int tmpP;
        std::cin >> tmpS >> tmpP;
        book.emplace_back(tmpS,100-tmpP,i+1);
    }
    sort(begin(book),end(book));
    
    for (int i = 0; i < n; i++) {
        std::cout << get<2>(book[i]) << std::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;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(1e5) + 5;
constexpr double EPS = 1e-9;
constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i > 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

ll n, A, B;
vector<ll> h;

bool check(ll x){
    ll cnt = 0;
    for(int i=0;i<n;i++){
        if(h[i] <= B*x) continue;
        else cnt += (h[i]-B*x-1)/(A-B)+1;
    }
    return cnt <= x;
}

int main() {
    cin >> n >> A >> B;
    h.resize(n);
    for(int i=0;i<n;i++) cin >> h[i];
    sort(h.begin(), h.end());

    ll ok = ll(1e9), ng = 0;
    while(abs(ok-ng)>1){
        ll mid = (ok+ng)/2;
        if(check(mid)){
            ok = mid;
        }
        else{
            ng = mid;
        }
    }
    cout << ok << endl;
    return 0;
}


Measured memory_bytes: 1024
n, m = list(map(int, input().split()))
ac = [0]*n
wa = [0]*n
for i in range(m):
    pi, si = input().split()
    if si == 'AC':
        ac[int(pi)-1] += 1
    elif ac[int(pi)-1] == 0:
        wa[int(pi)-1] += 1

nac = 0
nwa = 0

for i in range(n):
    if ac[i] > 0:
        nac += 1
        nwa += wa[i]

print(nac, nwa)        

    

Measured memory_bytes: 4596
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

bool isprime(int k)
{
    if(k<2) return 0;
    else if(k==2) return 1;
    if(k%2==0) return 0;
    for(int i=3;i*i<=k;i+=2)
    {
        if(k%i==0) return 0;
    }
    return 1;
}

int main()
{
	int n,m,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&m);
		if(isprime(m)) ans++;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3208
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count
from functools import lru_cache
from collections import defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    S = input()
    ans = 0
    for i in range(N-3+1):
        if S[i:i+3] == 'ABC':
            ans += 1
    print(ans)


main()


Measured memory_bytes: 6068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int>> vpii;
typedef pair<int, int> pii;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

map<ll, vi> mp;

int main(){
	int n; ll k; scanf("%d%lld", &n, &k);
	mp[0].EB(0);
	ll sm = 0;
	REP(i, n){
		ll a; scanf("%lld", &a);
		sm += a-1;
		DEBUG("%lld (%lld) -> %d\n", sm, sm%k, i+1);
		mp[sm % k].EB(i+1);
	}
	ll ans = 0;
	for(auto &p : mp){
		auto &v = p.second;
		v.EB(INT_MAX);
		int j = 0;
		REP(i, (int)v.size()-1){
			while(v[j] - v[i] < k) j++;
			DEBUG("%d: %d => %d: %d\n", i, v[i], j, v[j]);
			ans += j-i-1;
		}
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 22144
program ABC089B
    implicit none
    integer(8)::N,i
    integer(8)::result=4
    integer(8),dimension(4)::C=0!P,W,G,Yの順で
    character(1),allocatable,dimension(:)::S
    read(5,*)N
    allocate(S(N))
    read(5,*)(S(i),i=1,N)

    do i=1,N
        if(S(i)=="P")then
            C(1)=C(1)+1
        else if(S(i)=="W")then
            C(2)=C(2)+1
        else if(S(i)=="G")then
            C(3)=C(3)+1
        else if(S(i)=="Y")then
            C(4)=C(4)+1
        end if
    end do

    do i=1,4
        if(C(i)==0)then
            result=result-1
            exit
        end if
    end do

    if(result==4)then
        print'(A)',"Four"
    else
        print'(A)',"Three"
    end if
end program ABC089B

Measured memory_bytes: 512
#include<stdio.h>
int main()
{
    int a,b,c,d,f1,f2;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    if(c%b==0)
        f1=c/b;
    else
        f1=c/b+1;
    if(a%d==0)
        f2=a/d;
    else
        f2=a/d+1;
    if(f1<=f2)
        printf("Yes");
    else
        printf("No");
    return 0;
}


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

template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;

  int sz;
  vector< Monoid > seg;

  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }

  template< typename C >
  int find_subtree(int a, const C &check, Monoid &M, bool type) {
    while(a < sz) {
      Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
      if(check(nxt)) a = 2 * a + type;
      else M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }


  template< typename C >
  int find_first(int a, const C &check) {
    Monoid L = M1;
    if(a <= 0) {
      if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
      return -1;
    }
    int b = sz;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) {
        Monoid nxt = f(L, seg[a]);
        if(check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }

  template< typename C >
  int find_last(int b, const C &check) {
    Monoid R = M1;
    if(b >= sz) {
      if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
      return -1;
    }
    int a = sz;
    for(b += sz; a < b; a >>= 1, b >>= 1) {
      if(b & 1) {
        Monoid nxt = f(seg[--b], R);
        if(check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};


int main() {
    ll N,K;
    cin >> N >> K;
    vector<ll> sum(N+1,0);
    map<ll,ll> mp;
    mp[0];
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        a -=K;
        sum[i+1] = a+ sum[i];
        mp[sum[i+1]];
    }
    int index=0;
    for(auto itr = mp.begin();itr != mp.end();++itr){
        // cerr <<"itr=" << itr->first << endl;
        itr->second = index;
        index++;
    }
    SegmentTree<ll> seg(mp.size()+5,[](int a,int b){return (a+b);},0);
    ll ans =0;
    seg.update(mp[0],1);
    for(int i=0;i<N;i++){
        // cerr <<"t=" << sum[i+1] <<"mp=" <<mp[sum[i+1]] << endl;
        ans += seg.query(0,mp[sum[i+1]]+1);
        // cerr <<"query=" <<seg.query(0,mp[sum[i+1]]+1) << endl;
        seg.update(mp[sum[i+1]],seg.query(mp[sum[i+1]],mp[sum[i+1]]+1)+1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 21456
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int k, s, count=0;
	cin >> k >> s;
	for(int x=0; x<=k; x++){
		for(int y=0; y<=k; y++){
			if(s-x-y>=0 && s-x-y<=k)
				count++;
		}
	}
	cout << count << '\n';
	return 0;
}

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

int main() {
int  N,L;
    cin >> N >> L ;
  string A[110];
  for (int i=0; i<N; i++)
    cin >> A[i];
  
  sort (A,A+N) ;
  string B;
    for (int i=0; i<N; i++){
    B += A[i] ;
    }
  cout << B << endl;  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n){
        cin >> a[i];
    }
    int next = 1;
    int tmp = 0;
    bool can = false;
    rep(i,n){
        if(next==a[i]){
            next++;
            can = true;
        }else{
            tmp++;
        }
    }
    if(can){
        cout << tmp << endl;
    }else{
        cout << -1 << endl;
    }

}


Measured memory_bytes: 1024
loop do
  h, w = gets.chomp.split.map(&:to_i)
  break if h == 0 && w == 0
  for j in 0..(h - 1) do
    s = ""
    for i in 0..(w - 1) do
      s += (i == 0 || i == w - 1 || j == 0 || j == h - 1) ? "#" : "."
    end
    puts s
  end
  puts "\n"
end


Measured memory_bytes: 7264
#include <bits/stdc++.h>
using namespace std;
template <class T = int> using V = vector<T>;
template <class T = int> using VV = V< V<T> >;

struct Sparse2DSegmentTree {
  using T = int;
  static T op(const T& a, const T& b) { return max(a, b); }
  static constexpr T e() { return -1; }

  struct SegmentTree {
    const int n;
    V<T> t;
    SegmentTree(int _n) : n(_n), t(2 * n, e()) {}
    T& operator[](int i) { return t[i + n]; }
    T acc(int l, int r) const {
      T res = e();
      for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = op(res, t[l++]);
        if (r & 1) res = op(res, t[--r]);
      }
      return res;
    }
    void set(int i, const T& a) {
      t[i += n] = a;
      while (i >>= 1) t[i] = op(t[2 * i], t[2 * i + 1]);
    }
  };
  const int n;
  V<SegmentTree> st;
  VV<> ys;
  Sparse2DSegmentTree(int _n) : n(_n), ys(2 * n) {}
  void preset(int x, int y) {
    for (x += n; x; x >>= 1) ys[x].push_back(y);
  }
  void build() {
    for (auto&& v : ys) {
      sort(begin(v), end(v));
      v.erase(unique(begin(v), end(v)), end(v));
      st.emplace_back(v.size());
    }
  }
  int zip(int x, int y) const { return lower_bound(begin(ys[x]), end(ys[x]), y) - begin(ys[x]); }
  T acc(int x0, int x1, int y0, int y1) const {
    T res = e();
    for (x0 += n, x1 += n; x0 < x1; x0 >>= 1, x1 >>= 1) {
      if (x0 & 1) res = op(res, st[x0].acc(zip(x0, y0), zip(x0, y1))), ++x0;
      if (x1 & 1) --x1, res = op(res, st[x1].acc(zip(x1, y0), zip(x1, y1)));
    }
    return res;
  }
  void set(int x, int y, const T& a) {
    x += n, st[x].set(zip(x, y), a);
    while (x >>= 1) {
      T l = st[2 * x].acc(zip(2 * x, y), zip(2 * x, y + 1));
      T r = st[2 * x + 1].acc(zip(2 * x + 1, y), zip(2 * x + 1, y + 1));
      st[x].set(zip(x, y), op(l, r));
    }
  }
};

constexpr int lim = 1e5;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  struct Rec {
    int a, b, c, d;
  };
  vector< vector<Rec> > rec(lim);
  Sparse2DSegmentTree st(lim);
  for (int i = 0; i < n; ++i) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    --a, --b, --c, --d;
    rec[b].emplace_back(Rec{a, b, c, d});
    st.preset(a, c);
  }
  st.build();
  struct Query {
    int id, x, y, z, w;
  };
  vector< vector<Query> > qs(lim);
  for (int i = 0; i < q; ++i) {
    int x, y, z, w;
    cin >> x >> y >> z >> w;
    --x, --y, --z, --w;
    qs[y].emplace_back(Query{i, x, y, z, w});
  }
  vector<bool> res(q);
  for (int t = lim; t--; ) {
    for (auto e : qs[t]) {
      res[e.id] = st.acc(e.x + 1, e.y, e.z + 1, e.w) > e.w;
    }
    for (auto e : rec[t]) {
      st.set(e.a, e.c, e.d);
    }
  }
  for (auto e : res) {
    cout << (e ? "Yes" : "No") << '\n';
  }
}



Measured memory_bytes: 40464
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

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; }
typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }


std::vector<long long> Eratosthenes(long long N) {
  std::vector<long long> arr(N+1);
  for(long long i = 0; i <= N; i++) arr[i] = 1;
	for(long long i = 2; i <= std::sqrt(N); i++) {
    if(arr[i]) for(long long j = 0; i * (j + 2) <= N; j++) arr[i *(j + 2)] = 0;
  }

  std::vector<long long> rtn;
	for(long long i = 2; i <= N; i++){
		if(arr[i]) rtn.push_back(i);
	}
  return rtn;
}

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  ll X; std::cin >> X;
  auto L = Eratosthenes(2*X+1);
  auto k = std::lower_bound( all(L), X );
  std::cout << *k << std::endl;
  return 0;
}


Measured memory_bytes: 2176
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;
 
int main(){
    int N,K;

    cin >> N >> K;

    int n = (N - 1) * (N - 2) / 2;

    if(N <= 2){
        if(K == 0){
            cout << 1 << endl;
            cout << 1 << ' ' << 2 << endl;
            return 0;
        }

        cout << -1 << endl;
        return 0;
    }
    if(n < K){
        cout << -1 << endl;
        return 0;
    }

    cout << (n - K) + (N - 1) << endl;

    for(int i = 1;i < N;i++){
        cout << 1 << ' ' << i + 1 << endl;
    }

    int cnt = n - K;
    for(int i = 1;i < N;i++){
        for(int j = i + 1;j < N;j++){
            if(cnt == 0)return 0;
            cout << i + 1 << ' ' << j + 1 << endl;
            cnt--;
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;


const int MAX_M = 15;
int N, H[10];

double dp[2][(1 << MAX_M) + 1];

int solve() {
	int big=0, small=0;
	for (int i = 0; i < 10; i++) {
		if (big < small) swap(big, small);
		if (H[i] < small) {
			printf("NO\n");
			goto JUMP;
		}

		if (H[i] > big) big = H[i];
		else if (H[i] > small) small = H[i];

	}
	printf("YES\n");
JUMP:
	return 0;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> H[j];
		}
		solve();
	}

	
	return 0;
}

Measured memory_bytes: 1116
a=gets.to_i;
b=gets.to_i;
c=gets.to_i;
d=gets.to_i;
e=gets.to_i;
k=gets.to_i;
puts b-a <= k && c-a <= k&& d-a <= k && d-a <= k && e-a <= k && c-b <=k && d-b <= k && e-b <= k && d-c <=k && e-c <= k && e-d <= k ? "Yay!" : ":("

Measured memory_bytes: 1788