akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
typedef long long ll;
#define INF 100000000
#define MOD 100000007
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
using namespace std;
int main(void){
    int n;
    cin>>n;
    int h[n];
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    int max_height=h[0];
    int ans=0;
    for(int i=0;i<n;i++){
        if(h[i]>=max_height){
            ans++;
            max_height=h[i];
        }
    }
    cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N, M;
	string S;
	cin >> N >> M >> S;
	vector< vector<int> > G(2*N);
	for(int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		if(S[u] == S[v]) {
			G[2*u].push_back(2*v+1);
			G[2*v].push_back(2*u+1);
		}
		else {
			G[2*u+1].push_back(2*v);
			G[2*v+1].push_back(2*u);
		}
	}
	vector<int> deg(2*N, 0);
	for(int i = 0; i < 2*N; i++) ALL_THE(G[i], it) deg[*it]++;
	queue<int> q;
	for(int i = 0; i < 2*N; i++) if(deg[i] == 0) q.push(i);
	int proc = 0;
	while(!q.empty()) {
		proc++;
		ALL_THE(G[q.front()], it) {
			deg[*it]--;
			if(deg[*it] == 0) q.push(*it);
		}
		q.pop();
	}
	cout << ((proc < 2*N) ? "Yes\n" : "No\n");
	return 0;
}

// look at my code
// my code is amazing


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


int main()
{
    string s1,s2;
    cin >> s1 >> s2;
    for (int i = 0 ; i<3;i++)
        if (s1[i]!=s2[2-i])
    {
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<"YES"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int Max = 1000000;
long M = 1000000007;

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

  long cnt[65];
  for(int k=0;k<65;k++) cnt[k] = 0;

  ll tmp;
  for(int i=0;i<N;i++){
    cin >> tmp;
    int k = 0;
    while(tmp){
      cnt[k] += tmp%2;
      tmp /= 2;
      k++;
    }
  }

  ll ans = 0;
  ll r = 1;
  for(int k=0;k<65;k++){
    ll a = r%M;
    a = (a*cnt[k])%M;
    a = (a*(N-cnt[k]))%M;
    ans += a;
    ans = ans%M;
    r *= 2;
  }
    
  cout << ans%M <<endl;
  return 0;
}




Measured memory_bytes: 384
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int m_x = 0;
        String s = sc.next();
        String t = sc.next();
        
        for(int i=0;i<s.length()-t.length()+1;i++){
            String sub = s.substring(i,i+t.length());
            int c = monmo(sub,t);
            if(m_x < c)m_x = c;
        }
        
        System.out.println(t.length()-m_x);
    }
    
    static int monmo(String sub,String t){
        int count=0;
        String subArray[] = sub.split("");
        String tArray[] = t.split("");
        for(int i=0;i<t.length();i++){
            //char subA = sub.charAt(i);
            //char tA = t.charAt(i);
            if(subArray[i].equals(tArray[i]))count++;
            //if(subA == tA)count++;
        }
        
        return count;
    }
}


Measured memory_bytes: 57068
#include "bits/stdc++.h"

using namespace std;

//------------------------------- Libraries --------------------------------//

//------------------------------- Type Names -------------------------------//

using i64 = int_fast64_t;

using seika = string;
//akari : 1D, yukari : 2D, maki : 3D vector
template <class kizuna>
using akari = vector<kizuna>;
template <class yuzuki>
using yukari = akari<akari<yuzuki>>;
template <class tsurumaki>
using maki = akari<yukari<tsurumaki>>;
//akane : ascending order, aoi : decending order
template <class kotonoha>
using akane = priority_queue<kotonoha, akari<kotonoha>, greater<kotonoha>>;
template <class kotonoha>
using aoi = priority_queue<kotonoha>;

//------------------------------- Dubug Functions ---------------------------//
inline void print()
{
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest)
{
    cout << first << ' ';
    print(rest...);
}
//------------------------------- Solver ------------------------------------//

void solve()
{
    seika s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n - 1; i++)
    {
        if (s[i] == s[i + 1])
        {
            print(i + 1, i + 2);
            return;
        }
    }
    for (int i = 0; i < n - 2; i++)
    {
        if (s[i] == s[i + 2])
        {
            print(i + 1, i + 3);
            return;
        }
    }
    print(-1, -1);
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define repe1(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
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;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << max(a*b, c*d) << "\n";
}


Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = input()
k = inp()
n = len(s)
t = []
for i in s:
    t.append(ord(i) - ord('a'))
se = set()
for i in range(26):
    for j in range(n):
        if t[j] == i:
            for l in range(j,min(j+k,n)):
                tmp = s[j:l+1]
                if tmp == '':
                    continue
                se.add(tmp)
    if len(se) >= k:
        break
res = sorted(list(se))
print(res[k-1])

Measured memory_bytes: 65516
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;
int main(){
    int n, k;
    string s;
    cin >> n >> k >> s;
    s[k-1] = tolower(s[k-1]);
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,d = readInts()
xy = [readInts() for i in range(n)]

ans = 0
for x,y in xy:
	if d**2>=x**2+y**2:
		ans+=1

print(ans)

Measured memory_bytes: 45652
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
typedef double dd;
#define For(i,j,k) for (int i=(int)j;i<=(int)k;++i)
#define Forr(i,j,k) for (int i=(int)j;i>=(int)k;--i)
#define Set(a,p) memset(a,p,sizeof(a))
using namespace std;

template<typename T>bool chkmax(T &a,T b) { return a<b?a=b,1:0; }
template<typename T>bool chkmin(T &a,T b) { return a>b?a=b,1:0; }

const int maxn=1e5+1e2;
char s[maxn];
int n;

inline void file() {
	freopen("ARC059D.in","r",stdin);
	freopen("ARC059D.out","w",stdout);
}

inline int read() {
	int x=0,p=1;
	char c=getchar();
	while (!isdigit(c)) { if (c=='-') p=-1; c=getchar();}
	while (isdigit(c)) { x=(x<<1)+(x<<3)+(c-'0'); c=getchar();}
	return x*p;
}

int main() {
//	file();
	scanf("%s",s+1); n=strlen(s+1);
	For (i,1,n-1)
		if (s[i]==s[i+1]) {
			printf("%d %d\n",i,i+1); return 0;
		}
	For (i,1,n-2)
		if (s[i]==s[i+2]) {
			printf("%d %d\n",i,i+2); return 0;
		}
	puts("-1 -1");
	return 0;
}

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

#define st first
#define nd second
#define pb push_back
#define mp make_pair
typedef pair< int ,int > pii;
typedef vector< pii > vii;
typedef long long ll;
typedef map<int,int> mii;
typedef set<pii> sii;
typedef set<int> si;
typedef vector< int > vi;

const ll MOD = 119 << 23 | 1;

ll gcd(ll x, ll y){
    if(!y)
        return x;
    return gcd(y,x%y);
}

ll power(ll x, ll y)
{
    ll res = 1ll;     // Initialize result
    x%=MOD;
    if(x==0)
        return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % MOD;

        // y must be even now
        y = y>>1ll; // y = y/2
        x = (x*x) % MOD;
    }
    return res;
}

ll inv(ll x) {
    ll r = 1ll, t = x, k = MOD - 2ll;
    while (k) {
        if (k & 1ll) r = (long long) r * t % MOD;
        t = (long long) t * t % MOD;
        k >>= 1;
    }
    return r;
}

const int nax = 2e5+13;

int ktory=0;
int n;
vector<int>l;
bool stop=false;

void wypisz(int pop, int pos,int dl){
    for(int i=max(0,pop-1); i<=min(9,pop+1); i++){
        l[pos]=i;
        if(pos==dl-1){
            ktory++;
            //cout << ktory<<endl;
            if(ktory==n){
                for(auto el:l)
                    cout << el;
                cout << endl;
                stop=true;
            }
            if(stop)
                return;
            //return;
        }else{
            wypisz(i,pos+1,dl);
            if(stop)
                return;
        }
    }
}

void read(){
    cin >> n;
    if(n<=9){
        cout << n;
        return;
    }
    n-=9;
    for(int dl=2; dl<11; dl++){
        l.resize(dl);
        for(int i=1; i<=9; i++){
            l[0]=i;
            wypisz(i,1,dl);
            if(stop)
                return;
        }
    }
}

void solve(){

}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int T=1;
    //cin >> T;
    for(int i=1; i<=T; i++){

        read();
        //cout << "Case #"<<i<<": ";
        solve();
    }

    return 0;
}


Measured memory_bytes: 256
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.Maybe

import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.Maybe

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  [n, r] <- getIntList
  print $ if n >= 10 then r else r + 100*(10-n)

Measured memory_bytes: 380
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class MainClass
{
	public const long Giri = 1000000007;
	public const long DpInf = 99999999999;
	public static void Main(string[] args)
	{
		var a = Input();
		var n = a[0].ToLong();
		var k = a[1].ToInt();
		long t = 1;
		long i = 0;
		for(;t <= n;i++)
		{
			t *= k;
		}
		Console.WriteLine(i);
	}
	
	
	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str, int offset = 0)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt() + offset;
		return r;
	 }
}


Measured memory_bytes: 13140
#include <stdio.h>
#define N 1000

int main()
{
    int A[N];
    int num,v;
    int i, j, k;

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

    for (i=0; i < num; i++) {
        v = A[i];
        j = i-1;
        while (j >= 0 && A[j] > v) {
            A[j+1] = A[j];
            j--;
        }

        A[j+1] = v;

        for(k = 0; k < num; k++){
            if(k)printf(" ");
            printf("%d",A[k]);
            }   
        printf("\n");
        }
    return 0;
}



Measured memory_bytes: 2108
import java.util.Scanner;

public class Main {

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

        final int A = sc.nextInt();
        final int B = sc.nextInt();

        int ans = 0;
        for (int i = A; i <= B; i++) {
            String s = String.valueOf(i);
            String reverseS = new StringBuffer(s).reverse().toString();
            if (s.equals(reverseS)) ans++;
        }
        System.out.println(ans);
    }
}


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

struct UnionFind
{
    vector<ll> data;
    UnionFind(ll size) : data(size, -1) {}
    bool unionSet(ll x, ll y)
    {
        x = root(x);
        y = root(y);
        if (x != y)
        {
            if (data[y] < data[x])
                swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool findSet(ll x, ll y)
    {
        return root(x) == root(y);
    }
    ll root(ll x)
    {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    ll size(ll x)
    {
        return -data[root(x)];
    }
};
int main()
{
ll n,m;
cin >> n>>m;
if(m%2){
    cout << -1 << endl;
    return 0;
}
UnionFind arr(n);
set<ll> G[n];
vector<vector<ll>> g(n);
bool see[n]={};
rep(i, m)
{
    ll a,b;
    cin >> a>>b;
    G[a-1].insert(b-1);
    if(!arr.findSet(a-1,b-1)){
        G[b-1].insert(a-1);
        arr.unionSet(a-1,b-1);
        g[a-1].push_back(b-1);
        g[b-1].push_back(a-1); 
    }
    else cout << a << " " << b << endl;
}
vector<ll> ar;
ar.push_back(0);
see[0]=1;
ll par[n]={};
rep(i,n-1){
    rep(j,g[ar[i]].size()){
        if(!see[g[ar[i]][j]]){
            ar.push_back(g[ar[i]][j]);
            see[g[ar[i]][j]]=1;
            par[g[ar[i]][j]]=ar[i];
        }
    }
}
rep(i,n-1){
    if(G[ar[n-i-1]].size()%2==0){
        cout << ar[n-i-1]+1 << " " << par[ar[n-i-1]]+1 << endl;
        G[par[ar[n-i-1]]].erase(ar[n-i-1]);
    }
    else{
        cout << par[ar[n-i-1]]+1 << " " << ar[n-i-1]+1 << endl;
    }
}


return 0;
}


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

int d,g;
pair<int,int> pc[11];
int ans=INT_MAX;

void bitSearch(){
    for(int bit=0;bit<(1<<d);bit++){
        int sum=0,cnt=0,max=-1;
        for(int i=0;i<d;i++){
            if(bit&(1<<i)){
                sum+=100*(i+1)*pc[i].first+pc[i].second;
                cnt+=pc[i].first;
            }else 
                max=i;
        }
        if(sum<g){
            int sum1=100*(max+1);
            int need=(g-sum+sum1-1)/sum1;
            if(need>=pc[max].first)
                continue;
            cnt+=need;
        }
        ans=min(ans,cnt);
    }
}

void solve(){
    bitSearch();
    cout << ans << endl;
}

int main(void) {
    cin >> d >> g;
    for(int i=0;i<d;i++)
        cin >> pc[i].first >> pc[i].second;

    solve();
    return 0;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    int n;
    cin>>n;
    set<ll> sll;
    rep(i,n){
        ll a;
        cin>>a;
        if(sll.find(a)==sll.end()) sll.insert(a);
        else sll.erase(a);
    }
    cout<<sll.size()<<endl;
    return 0;
}

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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

#include <bits/stdc++.h>
using namespace std;

static const ll INF = 1e15;

static const ll mod = 1e9 + 7;

ll n;
vector<ll> vs;
vector<ll> wes;
vector<map<ll,ll>> memo;

ll dfs(ll node, ll les) {
    if (node <= min(1LL << 10, n)) {
        if (les == 0) return 0;
        auto& c = memo[node];
        auto f = c.upper_bound(les);
        std::advance(f, -1);
        return f->second;
    }
    auto a = dfs(node/2, les);
    if (les >= wes[node]) {
        auto b = dfs(node / 2, les - wes[node]);
        b += vs[node];
        return max(a, b);
    }
    return a;
}

int main() {
    cin >> n;
    vs.resize(n + 1);
    wes.resize(n + 1);
    memo.resize(n + 1);
    rep(i, n) {
        cin >> vs[i + 1] >> wes[i + 1];
    }
    memo[1][0] = 0;
    memo[1][wes[1]] = vs[1];
    if (n > 1) {
        vector<P> buffer;
        buffer.reserve(n);
        for (int i = 2; i <= min(1LL<< 10, n); i++) {
            buffer.clear();
            const auto& prev = memo[i / 2];
            for (auto p : prev) {
                buffer.emplace_back(p);
                buffer.emplace_back(p.first + wes[i], p.second + vs[i]);
            }
            sort(buffer.begin(), buffer.end());
            ll pv = -1;
            auto& child = memo[i];
            for (auto p : buffer) {
                if (pv < p.second) {
                    child[p.first] = p.second;
                    pv = p.second;
                }
            }
        }
    }
    int q;
    cin >> q;
    vector<ll> ans;
    rep(_, q){
        int v, l;
        cin >> v >> l;
        ll u = dfs(v, l);
        ans.push_back(u);
    }
    rep(i, q) {
        cout << ans[i] << endl;
    }
	return 0;
}
	

Measured memory_bytes: 62752
import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

R = []
for x in X:
    SL, SR, TL, TR = 10**20, 10**20, 10**20, 10**20
    i = bisect.bisect_left(S, x)
    if i != 0:
        SL = x-S[i-1]
    if i != A:
        SR = S[i]-x

    j = bisect.bisect_left(T, x)
    if j != 0:
        TL = x-T[j-1]
    if j != B:
        TR = T[j]-x

    ans = min(max(SL, TL), min(2*SL+TR, SL+2*TR),
              min(2*TL+SR, TL+2*SR), max(SR, TR))
    R.append(ans)
print(*R, sep='\n')


Measured memory_bytes: 21820
#include <bits/stdc++.h>
 
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n)  for(int i=0;i<(n);++i)
#define REPr(i, n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m, n) for(int i = (n);i >=(m);--i)
#define PB push_back
#define MP make_pair
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x, y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
/* (๑╹◡╹) */
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll MOD = 1000000007;
template<class T>
inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
 /* (๑╹◡╹)(๑╹◡╹)(๑╹◡╹)*/
template<class T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
/* (๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹) */
///////////////////////////////////////////////


int main() {
int ans = 0;
	int X,A; cin >> X >> A;
	if(X >= A){ans = 10;}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

   vector <int> A(n+2);

   for(int i = 0; i < n; i++) {
        cin >> A[i];
   }

   long long stool = 0;
   for(int i = 1; i < n; i++) {
        if(A[i] < A[i-1]) {
            stool += (A[i-1] - A[i]);
            A[i] = A[i-1];
        }
   }

   cout << stool << endl;
}


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

int main() {
    int i, x, y;
    i = 1;
    while (1) {
        cin >> x >> y;
        if (x == 0 && y == 0) break;
        if (x <= y) {
            cout << x << " " << y << "\n";
        }
        if (x > y){
            cout << y << " " << x << "\n";
        }
        i++;
    }

    return 0;
}

Measured memory_bytes: 3052
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    set<pair<int, int>> st;
    multiset<int> mst;
    for (int i = 0; i < w; i++) {
        st.emplace(i, i);
        mst.emplace(0);
    }
    st.emplace(w, w);
    int inf = 1e9;
    mst.emplace(inf);
    for (int i = 0; i < h; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        vector<pair<int, int>> v;
        int c = -1;
        for (auto it = st.lower_bound({a, -1}); it != st.end(); it++) {
            pair<int, int> p = *it;
            if (a <= p.first && p.first <= b) {
                c = max(c, p.second);
                v.emplace_back(p);
            } else {
                break;
            }
        }
        for (auto p : v) {
            st.erase(p);
            mst.erase(mst.find((p.first == w ? inf : p.first - p.second)));
        }
        if (c != -1) {
            st.emplace(b, c);
            if (b == w) {
                b = inf;
                c = 0;
            }
            mst.emplace(b - c);
        }
        int res = *mst.begin();
        if (res >= 1e8) {
            cout << -1 << '\n';
        } else {
            cout << res + i + 1 << '\n';
        }
    }
    return 0;
}

Measured memory_bytes: 22372
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
      q: usize,
      h: usize,
      s: usize,
      d: usize,
      n: usize,
    }

    let m = min(q*4, min(h*2, s));
    let mut ans = n*m;
    ans = min(ans, n/2*d + n%2 * m);
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int f[90100],a[310],n,ans=1,sum=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i],ans=3ll*ans%mod;
	f[0]=1;
	for(int i=1;i<=n;i++) for(int j=90000;j>=0;j--)
		f[j]=(0ll+f[j]+f[j]+(j<a[i]?0:f[j-a[i]]))%mod;
	for(int i=(sum+1)/2;i<=90000;i++) ans=(ans+mod-3ll*f[i]%mod)%mod;
	if(sum%2==0)
	{
		for(int i=0;i<=90000;i++) f[i]=0;f[0]=1;
		for(int i=1;i<=n;i++) for(int j=90000;j>=a[i];j--) f[j]=(f[j]+f[j-a[i]])%mod;
		ans=(ans+3ll*f[sum/2])%mod;
	}
	cout<<ans<<endl;
}

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


int main(){
  int S, W;cin >> S >> W;
  if(S>W) cout << "safe" << endl;
  else    cout <<"unsafe" << endl;

  return 0;
}



Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<list>
#include <array>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807
#define INF I64_MAX
#define MOD 1000000007
#define MEM_SIZE = 1e5+5;

// vector<int> DP[MEM_SIZE]


void solve(void)
{

  int N;
  cin>>N;
  vector<string> str(N);
  vector<int> time(N);
  for (int i = 0; i < N; i++)
  {
    cin>>str[i];
    cin>>time[i];
  }

  int ANS = 0;
  string str2;
  cin>>str2;
  int check = 0;
  for (int i = 0; i < N; i++)
  {
    if(check ==1) ANS += time[i];
    if(str2 == str[i])check = 1;
  }

  cout<<ANS<<endl;
  
  
  
  return;  
}



int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  // std::cout << std::fixed;
  // std::cout << std::setprecision(8);

  solve();

 
  return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long  
#define pb push_back

		   //       |----|       /\      |    |   -----   |
		   //       |   /       /  \     |    |     |     |
		   //       |--/       /----\    |----|     |     |
		   //       |   \     /      \   |    |     |     |
		   //       |    \   /        \  |    |   -----   -------
int n;
int32_t main()
{
	IOS;
	cin>>n;
	int ans=0;
	for(int i=1;i*i<n;i++)
	{
		if(n%i==0)
		{
			if(n/(n/i-1)==n%(n/i-1))
			ans+=n/i-1;
		}
	}
	cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define itn int
#define REP(i, n) for (int i = 0; i < n; i++)
#define IREP(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(a, b) for (int i = a; i < b + 1; i++)
#define all(a) a.begin(),a.end()
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;

signed main() {
	string s;
	cin >> s;
	int tmp=0;
	int ans=0;
	for(int a=0;a<(1<<(s.size()-1));a++){
		for(int i=0;i<s.size();i++){
			tmp=tmp*10+(s[i]-'0');
			if((a&(1<<i))!=0){
				ans+=tmp;
				tmp=0;
			}
		}
		ans+=tmp;
		tmp=0;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
N,M= list(map(int,input().split()))
end = []
start = []
for i in range(M):
    A,B = list(map(int,input().split()))
    end.append(B)
    start.append(A)
end_min = min(end)
start_max = max(start)
if start_max > end_min:
    print(0)
else:
    print(end_min-start_max+1)

Measured memory_bytes: 11064
def count_divisors(num, start, end):
    """
    num: positive int
    start: positive int
    end: positive int(end > start)
    returns numbers of devisors of i between start and end

    >>> count_divisors(80, 5, 14)
    3
    >>> count_divisors(12, 1, 4)
    4
    """
    count = 0
    for i in range(start, end+1):
        if num % i == 0:
            count += 1

    return count

if __name__ == '__main__':
    #import doctest
    #doctest.testmod()

    (a, b, c) = [int(i) for i in input().split(' ')]

    print(count_divisors(c, a, b))

Measured memory_bytes: 7752
# Problem https://atcoder.jp/contests/abc081/tasks/abc081_a
# Python 1st Try


def onecounter(input_square):
    result = 0
    if input_square[0] == '1':
        result = result + 1
    if input_square[1] == '1':
        result = result + 1
    if input_square[2] == '1':
        result = result + 1
    return result


if __name__ == "__main__":
    answer = onecounter(input())
    print(answer)
exit


Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Y = sc.nextInt();
		int x;
		int y;
		int z;

		for(x=0; x<=N; x++)
		{
			for(y=0;y<=N-x;y++)
			{
				 z = N - x - y;
				if(Y == 10000*x + 5000*y + 1000*z)
				{
					System.out.println(x + " " + y + " " +z);
					return;
				}
			}
		}
		System.out.println("-1 -1 -1");
	}
}


Measured memory_bytes: 23252
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	int n, a[3];
	cin >> n >> a[0] >> a[1] >> a[2];
	int l[n];
	for(int i=0; i<n; i++) cin  >> l[i];
	int ans=99999;
	for(int i=0; i<pow(4,n); i++){
		vector<int> v[3];
		for(int c=0, t=i; c<n; c++, t/=4){
			if(t%4<3) v[t%4].push_back(l[c]);
		}
		if(min({v[0].size(), v[1].size(), v[2].size()})==0) continue;

		int cost=0;
		for(int j=0; j<3; j++){
			cost+=(v[j].size()-1)*10;
			int sum=0;
			for(int k=0; k<v[j].size(); k++) sum+=v[j][k];
			cost+=abs(sum-a[j]);
		}
		ans=min(ans, cost);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
count0, count1 = 0, 0

for i in range(1, n+1):
    if i%k == 0:
        count0 += 1
    elif i%k == k/2:
        count1 += 1
ans = count0**3
if k%2 == 0:
    ans += count1**3
print(ans)


Measured memory_bytes: 9176
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
//#define int long long
using namespace std;
typedef pair<int,int>P;
#define fi first
#define se second

int dp[111][111][111];

signed main(){
	r(i,111)r(j,111)r(k,111)dp[i][j][k]=1e9;
	int a[3];
	r(i,3)cin>>a[i];
	dp[a[0]][a[1]][a[2]]=0;
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			for(int k=0;k<100;k++){
				if(dp[i][j][k]!=1e9){
					dp[i+1][j+1][k]=min(dp[i+1][j+1][k],dp[i][j][k]+1);
					dp[i+1][j][k+1]=min(dp[i+1][j][k+1],dp[i][j][k]+1);
					dp[i][j+1][k+1]=min(dp[i+1][j+1][k+1],dp[i][j][k]+1);
					dp[i+2][j][k]=min(dp[i+2][j][k],dp[i][j][k]+1);
					dp[i][j+2][k]=min(dp[i][j+2][k],dp[i][j][k]+1);
					dp[i][j][k+2]=min(dp[i][j][k+2],dp[i][j][k]+1);
				}
			}
		}
	}
	int ans=1e9;
	r(i,110)ans=min(ans,dp[i][i][i]);
	cout<<ans<<endl;
}

Measured memory_bytes: 5632
s = input()
n = len(s)+1
ans = 0
ls = [0]*n

tmp = 0

for i in range(n-1):
    if s[i] == "<":
        if i < n-2:
            if s[i+1] == "<":
                    tmp += 1
                    ans += tmp
            else:
                tmp += 1
                ans += tmp
                ls[i+1] = tmp
                tmp = 0
        else:
            tmp += 1
            ans += tmp
    else:
        tmp = 0
tmp = 0

for i in range(n-1):
    if s[n-i-2] == ">":
        if n-i-2 > 0:
            if s[n-i-3] == ">":
                tmp += 1
                ans += tmp
            else:
                tmp += 1
                if ls[n-i-2] < tmp:
                    ans += tmp - ls[n-i-2]
                tmp = 0
        else:
            tmp += 1
            ans += tmp

print(ans)

Measured memory_bytes: 7580
N = int(input())
A = [list(map(int,input().split())) for i in range(2)]

for i in range(1,N):
    A[0][i]=A[0][i]+A[0][i-1]

for i in range(N-2,-1,-1):
    A[1][i]=A[1][i]+A[1][i+1]

for i in range(N):
    A[0][i]+=A[1][i]

print(max(A[0]))

Measured memory_bytes: 62160
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
    int N;
    cin>>N;
    vector<int> A(N);

    for(int i=0; i<N; i++){
        cin >> A[i];
    }

    std::vector<size_t> indices(A.size());
    std::iota(indices.begin(), indices.end(), 0);

    // ソートする。
    std::sort(indices.begin(), indices.end(), [&A](size_t i1, size_t i2) {
        return A[i1] < A[i2];
    });

    for (auto v : indices)
        std::cout << v+1 << " ";

    return 0;
}

Measured memory_bytes: 2048
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, m, d[102][102] = {1};
    string s[102] = {};
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    if (s[0][0] == '#') d[0][0]++;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (i || j) {
        d[i][j] = 328;
        if (i) d[i][j] = min(d[i][j], d[i - 1][j] + (s[i - 1][j] != s[i][j]));
        if (j) d[i][j] = min(d[i][j], d[i][j - 1] + (s[i][j - 1] != s[i][j]));
    }
    if (s[n - 1][m - 1] == '#') d[n - 1][m - 1]++;
    cout << d[n - 1][m - 1] / 2;
}


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

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,ans=0; cin >> n;
	vector<int> v(2*n);
	for(auto &x:v) cin >> x;
	sort(v.begin(), v.end());
	for(int i=0;i<2*n;i+=2) ans += v[i];
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define inf LLONG_MAX
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

ll gcd(ll a, ll b) {
    while (b) {
        ll x = a, y = b;
        a = y, b = x % y;
    }
    return a;
}

vector<pair<ll, ll>> prime_factorize(ll n) {
    vector<pair<ll, ll>> res;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        ll num = 0;
        while (n % p == 0) { ++num; n /= p;}
        res.push_back({p, num});
    }

    if (n != 1) res.push_back({n, 1});
    return res;
}

int main()
{
    ll a, b; cin >> a >> b;
    ll g = gcd(a, b);
    auto pf = prime_factorize(g);
    cout << pf.size() + 1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3+5;
long long ans;
long long pref[MAXN];
long long dp[MAXN][MAXN];
int b[MAXN][210];
stack<int> s1;
int l[MAXN];
int r[MAXN];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        int x;cin>>x;
        pref[i] = pref[i-1]+x;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>b[i][j];
        }
    }
 
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            while(s1.size() && b[s1.top()][j]<b[i][j]){
                s1.pop();
            }
            
            if(s1.empty()){
                l[i] = 0;
            }else{
                l[i] = s1.top();
            }
            s1.push(i);
            
        }
        while(s1.size()){
            s1.pop();
        }
        for(int i=n;i>=1;i--){
            while(s1.size() && b[s1.top()][j]<b[i][j]){
                s1.pop();
            }
            if(s1.empty()){
                r[i] = n+1;
            }else{
                r[i] = s1.top();
            }
            s1.push(i);
            
        }
        for(int i=1;i<=n;i++){
            dp[l[i]+1][i]+=b[i][j];
            dp[i+1][i]-=b[i][j];
            dp[l[i]+1][r[i]]-=b[i][j];
            dp[i+1][r[i]]+=b[i][j];
            
            //cout<<i<<" "<<j<<" "<<l[i][j]<<" "<<r[i][j]<<endl;
        }
        while(s1.size()){
            s1.pop();
        }
        
    }
    while(s1.size()){
        s1.pop();
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j] += dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
            if(i<=j){
                ans = max(ans,(long long)dp[i][j]-(long long)pref[j]+(long long)pref[i]);
            }
            
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 199936
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
    int n, i, ans=0;
    scanf("%d", &n);
    int p[n];
    for(i=0; i<n; i++) scanf("%d", &p[i]);

    for(i=1; i<n-1; i++)
    {
        if(p[i-1]<p[i] && p[i]<=p[i+1]) ans++;
        else if(p[i-1]>=p[i] && p[i]>p[i+1]) ans++;
        else if(p[i-1]<p[i] && p[i-1]==p[i+1]) ans++;
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define NIL = -1;
#define all(x) x.begin(),x.end()
const ll INF = 1e9;
const ll INFL = 1e18;
const ll mod = 1e9 + 7;
 
int digit(ll x) {
    int digits = 0;

    while(x > 0){
        x /= 10;
        digits++;
    }

    return digits;
}
 
ll gcd(long long a,long long b) {
    if (a < b) swap(a,b);
    if (b == 0) return a;
    
    return gcd(b,a%b);
}

bool is_prime(long long N){
    if (N == 1) return false;
    for (long long i = 2;i * i <= N;i++){
        if (N % i == 0) return false;
    }
    return true;
}
 
ll lcm(ll a,ll b){
    return ((a * b == 0)) ? 0 : (a / gcd(a,b) * b);
}
 
double DegreeToRadian(double degree){
    return degree * M_PI / 180.0;
}
 
 
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
 
 
///////////////////////////////////////////////////////////////////////////////////

int main(){
    long long x;
    cin >> x;
    long long sum = 0;
    int cnt = 0;
    for (int i = 1;i <= x;i++){
        sum += i;
        cnt++;
        if (sum >= x){
            break;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 3568
N=int(input())
b = list(map(int, input().split()))

ans=[]

#delete N times
for i in range(N):
    #j:index of delete + 1(ans base)
    j = False
    for k in range(len(b)-1,-1,-1):
        if b[k] == k + 1:
            j = True
            del b[k]
            ans.append(k+1)
            break
    if not j:
        print(-1)
        import sys
        sys.exit()

for i in range(len(ans) - 1, -1, -1):
    print(ans[i])

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main(void){
    int K,S, ans=0;
    cin >> K >> S;
    
    for(int x=0; x <= K; x++){
        for(int y=0; y <= K; y++){
            int z = S - x - y;
            if(0 <= z and z <= K){
                ans += 1;
            }
        }
    }
    cout << ans;
}


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

int sum[100001];
int main() {
	int n, t; scanf("%d%d", &n, &t);
	rep(i, n) {
		int l, r; scanf("%d%d", &l, &r);
		sum[l]++; sum[r]--;
	}
	int Max = sum[0];
	for (int i = 1; i <= t; i++) {
		sum[i] += sum[i - 1];
		Max = max(Max, sum[i]);
	}
	printf("%d\n", Max);
}

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

using namespace std;

long long h,w;

int main(){
    scanf("%lld%lld",&h,&w);
    if(h==1||w==1){
        puts("1");
    }else{
        long long t=h*w;
        if(t%2){
            printf("%lld\n",t/2+1);
        }else{
            printf("%lld\n",t/2);
        }
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int N[] = new int[n];
		int count = 0;
		
		for (int i = 0; i <= n - 1; i++) {
			int x = scanner.nextInt();
			N[i] = x;
		}
        for (int i = 0; i < n - 1; i++) {
            for (int j = n - 1; j > i; j--) {
                if (N[j - 1] > N[j]) {
                    int a = N[j - 1];
                    N[j - 1] = N[j];
                    N[j] = a;
                    count++;
                }
            }
        }
		for (int k = 0; k < n - 1; k++) {
			System.out.print (N[k] + " ");
			}
		System.out.println (N[n - 1]);
        System.out.println(count);
    }
}


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

int main()
{
	double x1, x2, y1, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	cout << fixed << setprecision(6) << sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) << endl;
	return 0;
}

Measured memory_bytes: 3256
n, m = map(int, input().split())
ans= 0
hs = list(map(int, input().split()))
ds = {}
ok = True
for i in range(m):
    a,b = map(int, input().split())
    if(a in ds):
        ds[a].append(b)
    if(b in ds):
        ds[b].append(a)
    if(a not in ds):
        ds[a] = [b]
    if(b not in ds):
        ds[b] = [a]
for i in range(1, n+1):
    if(i not in ds):
        ans +=1
    else:
        for l in ds[i]:
            if(hs[i-1] <= hs[l-1]):
                ok = False
        if(ok):
            ans +=1
        ok = True
print(ans)


Measured memory_bytes: 98148
S = input()
T = S[2:-1]
c = 0
U = ''
for t in T:
  if t =='C':
    c+=1
  elif t.isupper():
    print('WA')
    exit()
if S[0]=='A' and c==1 and S[1].islower() and S[-1].islower():
  print('AC')
else:
  print('WA')

Measured memory_bytes: 3060
def comb(n, r):
    if r<0 or r>n:
        return 0
    r=min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%MOD

MOD=10**9+7
MAXN=400000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

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

N, K=map(int, input().split())
if K>=N-1:
    print(comb(N*2-1, N))
else:
    ans=1
    for i in range(1, K+1):
        ans=(ans+(comb(N-1, i)*comb(N, i))%MOD)%MOD
    print(ans)

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

bool can(int N, int M, int V, int P, vector<int> A, int k){
	if(k < P){
		return true;
	}
	int i;
	if(V <= P){
		A[k] += M;
		for(i = 0; i < V - 1; i++){
			A[i] += M;
		}
		int count = 0;
		for(i = 0; i < N; i++){
			if(A[i] > A[k]){
				count++;
			}
		}
		if(count >= P){
			return false;
		}
		return true;
	}
	A[k] += M;
	for(i = 0; i < P - 1; i++){
		A[i] += M;
	}
	int count = 0;
	for(i = 0; i < N; i++){
		if(A[i] > A[k]){
			count++;
		}
	}
	if(count >= P){
		return false;
	}
	int sum = 0;
	for(i = P - 1; i < N; i++){
		if(i == k){
			continue;
		}
		sum += min(M, A[k] - A[i]);
	}
	if(sum >= (V - P) * M){
		return true;
	}
	else{
		return false;
	}
}

signed main(){
	int N, M, V, P, i;
	scanf("%lld%lld%lld%lld", &N, &M, &V, &P);
	vector<int> A(N);
	for(i = 0; i < N; i++){
		scanf("%lld", &A[i]);
	}
	for(i = 0; i < N; i++){
		A[i] = -A[i];
	}
	sort(A.begin(), A.end());
	for(i = 0; i < N; i++){
		A[i] = -A[i];
	}
	int l = -1, h, r = N;
	while(r - l > 1){
		h = (l + r) / 2;
		if(can(N, M, V, P, A, h)){
			l = h;
		}
		else{
			r = h;
		}
	}
	printf("%lld\n", r);
	return 0;
}

Measured memory_bytes: 1920
#include "bits/stdc++.h"

#define INF 99999999
#define FER 0.0000000001

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;

struct Edge
{
	int s, t, w;
	Edge(int s,int t,int w):s(s),t(t),w(w){}
	Edge() :Edge(-1, -1, -1) {}
	bool operator<(const Edge& e)const
	{
		return w != e.w ? w < e.w : (s != e.s ? s < e.s : t < e.t);
	}
};


struct P
{
	double x, y;
	P(double x, double y) :x(x), y(y) {}
	P() :P(0, 0) {}
	P operator+(const P& v)const
	{
		return P(x + v.x, y + v.y);
	}
	P operator-(const P& v)const
	{
		return P(x - v.x, y - v.y);
	}
	P operator*(const double v)const
	{
		return P(x*v, y*v);
	}
	bool operator==(const P& v)const
	{
		return abs(x - v.x) <= 0.0000000000001&&abs(y - v.y) <= 0.00000000000001;
	}
	bool operator!=(const P& v)const
	{
		return abs(x - v.x) > 0.0000000000001 || abs(y - v.y) > 0.00000000000001;
	}

	double dot(const P& v)const
	{
		return x*v.x + y*v.y;
	}
	double cross(const P& v)const
	{
		return x*v.y - y*v.x;
	}
	double length()const
	{
		return sqrt(x*x + y*y);
	}
	double length2()const
	{
		return (x*x + y*y);
	}

	bool operator<(const P& v)const
	{
		return x<v.x || (x == v.x) && y < v.y;
	}
	bool operator>(const P& v)const
	{
		return x>v.x || (x == v.x) && y > v.y;
	}
};

struct Rectangle
{
	int h;
	int p;
	Rectangle(int h,int p):h(h),p(p){}
};

int matrix[1400][1400];
int L[1400][1401];

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

	int H, W;
	cin >> H >> W;

	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cin >> matrix[i][j];
		}
		L[i][W] = 0;
	}

	for (int j = 0; j < W; j++)
	{
		int length = 0;
		for (int i = 0; i < H; i++)
		{
			if (matrix[i][j] == 1)
			{
				length = 0;
				L[i][j] = 0;
			}
			else
			{
				L[i][j] = ++length;
			}
		}
	}

	int ans = 0;
	W++;

	for (int k = 0; k < H; k++)
	{
		stack<Rectangle> rs;

		int tans = 0;
		for (int i = 0; i < W; i++)
		{
			if (rs.empty())
			{
				rs.push(Rectangle(L[k][i], i));
			}
			else
			{
				if (rs.top().h < L[k][i])
				{
					rs.push(Rectangle(L[k][i], i));
				}
				else if (rs.top().h>L[k][i])
				{
					int tp = i;
					while (!rs.empty() && rs.top().h>L[k][i])
					{
						Rectangle tr = rs.top();
						rs.pop();
						tans = max(tans, tr.h*(i - tr.p));
						tp = tr.p;
					}
					rs.push(Rectangle(L[k][i], tp));
				}
			}
		}

		ans = max(ans, tans);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 18488
num = gets.to_i

res = num == 0 ? "0" : ""

while num != 0 do
  current_bit = 0
  if num % 2 == 1
    current_bit = 1
    num -= 1
  end
  res.insert(0, current_bit.to_s)
  num /= -2
end

puts res
  



Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 

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


int main()
{
	int N, C; cin >> N >> C;
	vector<vector<long long>> d(C, vector<long long>(C));
	rep(i, 0, C - 1)rep(j, 0, C - 1) cin >> d[i][j];
	vector<vector<int>> c(N, vector<int>(N));
	rep(i, 0, N - 1)rep(j, 0, N - 1) cin >> c[i][j], --c[i][j];
	//(x+y)%3=0のマスの色を色iに塗り替えた時の違和感:zero[i]
	vector<long long> zero(C, 0), one(C, 0), two(C, 0);
	rep(i, 0, C - 1)rep(x, 0, N - 1)rep(y, 0, N - 1)
	{
		switch ((x + y) % 3)
		{
		case 0:
			zero[i] += d[c[x][y]][i];
			break;
		case 1:
			one[i] += d[c[x][y]][i];
			break;
		case 2:
			two[i] += d[c[x][y]][i];
			break;
		}
	}
	long long res = 10000000000;
	rep(i, 0, C - 1)rep(j, 0, C - 1)rep(k, 0, C - 1)
	{
		if (i != j && i != k && j != k)
		{
			res = min(res, zero[i] + one[j] + two[k]);
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 1280
from collections import Counter

N = int(input())
As = list(map(int, input().split()))

Bs = [i-A for i, A in enumerate(As)]
cnt = Counter(Bs)

ans = 0
for L in range(N):
    AL = As[L]
    cnt[L-AL] -= 1
    ans += cnt[L+AL]

print(ans)


Measured memory_bytes: 42848