akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

// @@ !! LIM()

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  vector A(N+1, 0LL);
  ll pos = 0;
  ll neg = 0;
  ll pos_idx = -1;
  ll neg_idx = -1;
  for (ll i = 1; i <= N; i++) {
    ll a; cin >> a;
    A.at(i) = a;
    if (a >= 0) {
      if (pos <= a) {
	pos_idx = i;
	pos = a;
      }
    }else {
      if (neg >= a) {
	neg_idx = i;
	neg = a;
      }
    }
  }
  cout << N + N - 1 << "\n";
  if (pos >= -neg) {
    for (ll i = 1; i <= N; i++) {
      cout << pos_idx << " " << i << "\n";
    }
    for (ll i = 1; i < N; i++) {
      cout << i << " " << i+1 << "\n";
    }
  }else {
    for (ll i = 1; i <= N; i++) {
      cout << neg_idx << " " << i << "\n";
    }
    for (ll i = N-1; i >= 1; i--) {
      cout << i+1 << " " << i << "\n";
    }
  }

  return 0;
}



Measured memory_bytes: 3620
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string.h>
#include<string>
#include<set>
#include<limits.h>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<functional>
#include<stack>
#include<deque>
#include<queue>
using namespace std;

signed main() {
	int ans = 0;
	int n, a, b; cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) {
		string c = to_string(i);
		int d = 0;
		for (char e : c) {
			d += e - '0';
		}
		if (d >= a&&d <= b)ans+=i;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INTINF = 1<<29;
const ll LLINF = 1LL<<61;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const int DX[8]={ 0, 1, 0,-1, 1, 1,-1,-1};
const int DY[8]={ 1, 0,-1, 0, 1,-1, 1,-1};


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if(a+b>c+d){
      cout << "Left" << endl;
  }else if(a+b<c+d){
      cout << "Right" << endl;
  }else{
      cout << "Balanced" << endl;
  }
}


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

typedef long long int ll;
const int mod = 1e9+7;
const ll inf = 1e18;
const double pi = 3.1415926535897932384626;

ll mpow(ll a,ll b){
    ll res=1;
    //a%=mod;
    while(b){
    	if(b%2) res=res*a; //%mod;
		a=a*a; //%mod;
		b/=2;
	}
	return res;
}

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

ll lcm(ll a,ll b){
	return b*a/gcd(a,b);
}

void solve(){
	//code
	int n;
	cin>>n;
	string s;
	cin>>s;
	int count=1;
	for(int i=0;i<n-1;i++){
		if(s[i]!=s[i+1])
			count++;
	}
	cout<<count;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	solve();
 	return 0;
}


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

struct Card {
  char suit;
  int value;
};

void selectionSort(vector<Card> &cards) {
  rep(i, cards.size() - 1) {
    int minj = i;
    for (int j = i; j < cards.size(); j++) {
      if (cards[j].value < cards[minj].value) minj = j;
    }
    if (minj != i) swap(cards[minj], cards[i]);
  }
}

void bubbleSort(vector<Card> &cards) {
  bool flag = true;
  while (flag) {
    flag = false;
    for (int i = cards.size() - 1; i > 0; i--) {
      if (cards[i].value < cards[i - 1].value) {
        swap(cards[i], cards[i - 1]);
        flag = true;
      }
    }
  }
}

void buildKeymap(vector<Card> cards, map<int, vector<char> > &keymap) {
  rep(i, cards.size()) keymap[cards[i].value].push_back(cards[i].suit);
}

bool isStable(vector<Card> sorted_cards, vector<Card> org_cards) {
  map<int, vector<char> > org_keymap, sorted_keymap;
  buildKeymap(org_cards, org_keymap);
  buildKeymap(sorted_cards, sorted_keymap);

  bool flag_stable = true;
  for (map<int, vector<char> >::iterator itr = org_keymap.begin();
       itr != org_keymap.end(); itr++) {
    int v = itr->first;
    rep(i, org_keymap[v].size()) {
      if (org_keymap[v][i] != sorted_keymap[v][i]) {
        flag_stable = false;
        break;
      }
    }
    if (!flag_stable) break;
  }
  return flag_stable;
}

void print_cards(vector<Card> cards) {
  rep(i, cards.size()) {
    if (i > 0) cout << " ";
    cout << cards[i].suit << cards[i].value;
  }
  cout << endl;
}

void print_is_stable(bool is_stable) {
  if (is_stable)
    cout << "Stable" << endl;
  else
    cout << "Not stable" << endl;
}

int main() {
  int n;
  cin >> n;
  vector<Card> org_cards(n), cards1(n), cards2(n);
  rep(i, n) cin >> org_cards[i].suit >> org_cards[i].value;
  rep(i, n) {
    cards1[i].suit = org_cards[i].suit;
    cards1[i].value = org_cards[i].value;
    cards2[i].suit = org_cards[i].suit;
    cards2[i].value = org_cards[i].value;
  }

  bubbleSort(cards1);
  bool is_stable_bubble = isStable(cards1, org_cards);
  print_cards(cards1);
  print_is_stable(is_stable_bubble);

  selectionSort(cards2);
  bool is_stable_selection = isStable(cards2, org_cards);
  print_cards(cards2);
  print_is_stable(is_stable_selection);

  return 0;
}



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

const int INF = 1e9;
int dp[10010];

signed main() {
    int h,n;
    cin >> h >> n;

    vector<P> a(n);
    rep(i,n){
        cin >> a[i].first >> a[i].second;
    }

    rep(i,10010) dp[i] = INF;
    dp[0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= h; j++){
            int nt = j + a[i].first;
            if(nt >= h) nt = h;
            dp[nt] = min(dp[nt], dp[j] + a[i].second);
        }
    }

    cout << dp[h] << endl;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod =  998244353

lim = 2*10**5
fact = [1]*(lim+1)
for n in range(1, lim+1):
	fact[n] = n*fact[n-1]%mod

fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


N, M, K = MAP()

ans = 0
for i in range(K+1):
	a = M*pow(M-1, N-1-i, mod)%mod*C(N-1, i)%mod
	ans = (ans+a)%mod

print(ans)


Measured memory_bytes: 25564
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <list>
#include <ctime>
#include <sstream>
#include <queue>
#include <stack>
#include <random>
#include <bitset>
#include <numeric>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define rep(x, b, e) for(int x=(b); x<(e); ++x)
#define ford(x, b, e) for(int x=((int)(b))-1; x>=(e); --x)
#define all(c) c.begin(),c.end()
#define sz(x) ((int)((x).size()))
#define pb push_back
#define st first
#define nd second
#define mp(x,y) make_pair(x,y)
typedef short int sint;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it) {
	*this << ((it != d.b) ? ", " : "") << *it;
  }
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int inf = 1e9 + 10;
const int nax = 1e5 + 10;
pii tab[nax];
int opt[nax];
int n;

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;
	rep(i, 0, n) {
		cin >> tab[i].st >> tab[i].nd;
	}
	sort(tab, tab + n, [&](const pii& a, const pii&b) {
		int v1 = a.st + a.nd, v2 = b.st + b.nd;
		if (v1 != v2) {
			return v1 < v2;
		}
		return a.st < b.st;
	});
	vi pom;
	pom.pb(-inf);
	opt[0] = 0;
	rep(i, 0, n) {
		opt[i+1] = opt[i];
		int kt = upper_bound(pom.begin(), pom.end(), tab[i].st - tab[i].nd) - pom.begin();
		// debug() << imie(i) imie(kt) imie(opt[kt]);
		opt[i+1] = max(opt[i + 1], opt[kt - 1] + 1);
		pom.pb(tab[i].st + tab[i].nd);
	}
	cout << opt[n] << endl;
}

Measured memory_bytes: 1916
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

ll N;
ll X[30], Y[30], P[30], dist[30];
long double eps = 1e-9;
ll ans[30];

void init_dist() {
  rep(i, 0, N) {
    ll d = INF;
    chmin(d, abs(X[i]));
    chmin(d, abs(Y[i]));
    dist[i] = d;
  }
}

void dfs(int cur, int cnt) {
  if (cur >= N) {
    ll score = 0;
    rep(i, 0, N) { score += dist[i] * P[i]; }
    chmin(ans[cnt], score);
    return;
  }

  dfs(cur + 1, cnt);

  ll cdist[30];
  rep(i, 0, N) {
    cdist[i] = dist[i];
    chmin(dist[i], abs(Y[i] - Y[cur]));
  }
  dfs(cur + 1, cnt + 1);

  rep(i, 0, N) { dist[i] = min(cdist[i], abs(X[i] - X[cur])); }
  dfs(cur + 1, cnt + 1);

  rep(i, 0, N) { dist[i] = cdist[i]; }
}

int main() {
  //
  cin >> N;
  rep(i, 0, N) { cin >> X[i] >> Y[i] >> P[i]; }

  init_dist();
  repe(i, 0, N) { ans[i] = INF; }

  dfs(0, 0);

  cout << ans[0] << "\n";
  repe(i, 1, N) {
    chmin(ans[i], ans[i - 1]);
    cout << ans[i] << "\n";
  }
}


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

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

  for (int i = 1; i < n; i++){
    cout << arr[n-i] << " ";
  }
  cout << arr[0] << endl;
  
  return 0;
}


Measured memory_bytes: 3012
import java.util.*;

public class Main {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();

        long digits = 0;
        long dsum = 0;
        for(int i=0; i<m; i++) {
            int d = sc.nextInt();
            long c = sc.nextLong();
            digits += c;
            dsum += c * d;
        }
        long res = digits - 1 + (dsum - 1)/9;

        System.out.println(res);
    }
}


Measured memory_bytes: 91552
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PPI;
typedef pair<ll,P> PIP;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
#define PQ(T) priority_queue<T,vector<T>,greater<T>>
#define PQ2(T) priority_queue<T>
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define REP(i,a,b) for(ll (i)=a;(i)<(ll)(b);++(i))
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) ((x)=min((x),(y)))
#define chmax(x,y) ((x)=max((x),(y)))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
#define DEBUG(x) cerr<<"line ("<<__LINE__<<")  "<<#x<<": "<<x<<endl;
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	ll a, b;
	cin>>a>>b;
	if(a>b) swap(a, b);
	ll c = 0;
	if(a==1){
		c = b-2;
		if(b==1) c = 1;
	} else {
		c = (a-2)*(b-2);
	}
	if(c<0) c = 0;
	cout<<c<<endl;
	return 0;
}


Measured memory_bytes: 256
//frog1-->akash_codex
#include<iostream>
#include<math.h>
typedef long long ll;
using namespace std;

int main(){
	ll n;
	cin>>n;
	ll height[n],dp[n];
	
	for(ll i=0;i<n;i++) cin>>height[i];
	dp[0]=0;
	dp[1]=abs(height[1]-height[0]);
	for(ll i=2;i<n;i++){
		dp[i]=min(dp[i-1]+abs(height[i]-height[i-1]),dp[i-2]+abs(height[i]-height[i-2]));
	}
	cout<<dp[n-1];
	return 0;
}

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

int p, w, g, y;

int main() {
    ios::sync_with_stdio(false);
    
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        char s;
        cin >> s;
        if (s == 'P')
            p++;
        else if (s == 'W')
            w++;
        else if (s == 'G')
            g++;
        else if (s == 'Y')
            y++;
    }
    
    if (p > 0 && w > 0 && g > 0 && y == 0)
        cout << "Three\n";
    else if (p > 0 && w > 0 && g > 0 && y > 0)
        cout << "Four\n";
    
    
    
    
    
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int i,n,x,l,sum=1,len=0;
	scanf("%d%d",&n,&x);
	for(i=0;i<n;i++){
		scanf("%d",&l);
		len+=l;
		if(len<=x)
			sum++;
		}
	printf("%d",sum);
	return 0;
}
			
	

Measured memory_bytes: 128
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int k = sc.nextInt();
        int[] sum = {a,b,c};

        for(int i =0;i<k;i++){
            Arrays.sort(sum);
            sum[2] *=2;
        }

        System.out.println(sum[0]+sum[1]+sum[2]);






      
    }
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define rep(i, n) FOR(i, 0, n)
#define repi(i, n) FOR(i, 1, n + 1)
#define pp(v) cerr << #v "=" << (v) << endl;
#define ppa(v) cerr << "----\n"; rep(i,v.size()) cout << #v << "[" << i << "] = " << v[i] << endl;
#define div_ceil(a,b) ((a) + ((b) - 1)) / (b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using Graph = vector<vector<int>>;
using ll = long long;

int main() {
  int n,k,x,y;cin>>n>>k>>x>>y;
  int ans = n > k ? k * x + (n-k) * y : n * x;
  cout << ans << endl;
}


Measured memory_bytes: 256
import math
N = int(input())
AB_MIN = 1000000000000

sqrtN = int(math.sqrt(N)) + 1

for a in range(1, sqrtN)[::-1] :
    if N % a == 0:
        b = N / a
        if AB_MIN > a + b - 2:
            AB_MIN = a + b - 2

if AB_MIN == 1000000000000:
    AB_MIN = N - 1

print(int(AB_MIN))

Measured memory_bytes: 3188
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<math.h>
#include<stdlib.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007

int N, heap[600000];

void maxheapify(int i){
    if(i > N / 2)return;
    int l = i * 2;
    int r = i * 2 + 1;
    int largest = i;
    if(heap[i] < heap[l] && l <= N){
        largest = l;
    }
    if(r <= N){
        if(heap[largest] < heap[r])largest = r;
    }
    if(largest != i){
        swap(heap[i], heap[largest]);
        maxheapify(largest);
    }
}

signed main(){
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> heap[i];
    }
    for(int i = N / 2; i >= 1; i--){
        maxheapify(i);
    }
    for(int i = 1; i <= N; i++){
        printf(" %lld", heap[i]);
    }
    printf("\n");


    return 0;
}

/*

*/


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

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()
#define endl        "\n"
#define repp(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a,b) 	for(int i=a;i<=b;i++)
#define IOS         ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N=1e5 + 5;

stack<char> s;

int32_t main()
{
	IOS;
	string ss;
	cin >> ss;
	int i;
	for(i=0;i<ss.size();i++)
	{
		if(ss[i]=='0' || ss[i]=='1')
		{
			s.push(ss[i]);
		}
		else if(s.size()>0)
			s.pop();	
	}
	vector<char> v;
	while(!s.empty())
	{
		char c= s.top();
		s.pop();
		v.pb(c);
	}
	reverse(all(v));
	for(char c:v)
	{
		cout << c;
	}
	cout << endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int count= 0;
    for(int i = 0;i<s.length()/2;i++){
      if(!(s.substring(i,i+1).equals(s.substring(s.length()-i-1,s.length()-i)))){
        count++;
      }
    }
    System.out.println(count);
  }
}


Measured memory_bytes: 35596
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <climits>
#include <cassert>
#include <algorithm>
#include <utility>

using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;
using VVI = vector<vector<long long int> >;


int main(void) {
    string s;
    cin >> s;
    if (s[1] == 'B') {
        s[1] = 'R';
    } else if (s[1] == 'R') {
        s[1] = 'B';
    }
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>

using namespace std;

int N;
int A[100005];

int main(void)
{
	cin >> N;
	for(int i = 0; i < N; i++) cin >> A[i];
	sort(A, A+N);
	
	int ans = 0;
	int prev = -1, cnt = 0;
	for(int i = 0; i < N; i++){
		if(A[i] != prev){
			if(cnt % 2) ans++;
			prev = A[i];
			cnt = 1;
		}else{
			cnt++;
		}
	}
	if(cnt % 2) ans++;
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
using namespace std;

signed main()
{
	int N, T;
	cin >> N >> T;

	int ans = T;
	int prev = 0;
	int temp;
	cin >> temp;
	for (int n = 0; n < N - 1; n++)
	{
		int t;
		cin >> t;
		int d = t - prev;
		prev = t;
		if (d <= T)
		{
			ans += T - (T - d);
		}
		else
		{
			ans += T;
		}
	}
	cout << ans << endl;
}


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

using namespace std;
int main() {
  int n, k;
  cin >> n >> k;
  int result = 1;
  for (int i = 0; i < n; i++) {
    int a = result * 2;
    int b = result + k;
    if (a < b)
      result = a;
    else
      result = b;
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#  --*-coding:utf-8-*--

def gcd(n, m):
    while m > 0:
        n, m = m, n%m

    return n

def f(M, A):
    lcm = 1

    for a in A:
        g = gcd(lcm, a)
        lcm = lcm*a//g

        if lcm > M:
            return 0

    for a in A:
        if lcm//a%2 == 0:
            return 0

    return (M-lcm)//(2*lcm) + 1
            


def main():
    N, M = map(int, input().split())
    A = list(map(lambda x:int(x)//2, input().split()))

    print(f(M,A))

    



if __name__ == '__main__':
    main()


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


int main(){
    int x;
    vector<int> nums;
    nums.resize(3,0);
    cin >> x;
    while( 0 <= --x ){
        int a,b,c;
        cin >> nums[0] >> nums[1] >> nums[2];
        sort(nums.begin(), nums.end());
        if( pow(nums[0], 2) + pow(nums[1], 2) == pow(nums[2], 2)){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }


    return 0;
}

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

int main()
{
	int n,i,temp,ans,a[100];
	cin >> n;
	for(i=0; i<n; i++)
		cin >> a[i];
	ans = 0;
	for(i=0; i<n; i++)
	{
		cin >> temp;
		a[i] -= temp;
		if(a[i] >= 0)
			ans += a[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <atcoder/all>
#include <bits/stdc++.h>
typedef long long int lld;
typedef unsigned long long int llu;
#define INF (lld)(9223372036854775807)
#define IINF (int)(2147483647)

using namespace std;
using namespace atcoder;

int main(void) {
  lld n, q;
  cin >> n >> q;
  dsu d(n);

  for (lld i = 0; i < q; i++) {
    lld t, u, v;
    cin >> t >> u >> v;
    if (t == 0) {
      d.merge(u, v);
    } else {
      if (d.same(u, v)) {
        cout << 1 << "\n";
      } else {
        cout << 0 << "\n";
      }
    }
  }
}


Measured memory_bytes: 4024
#include<stdio.h>
#include<string.h>
void rotstring(char str[])
{
    int l=strlen(str),temp[l],t,w=0;
    t=str[l-1];
    for(int i=1;i<l;i++)
    {
        temp[i]=str[i-1];

    }
    str[0]=t;
    for(int i=1;i<l;i++)
    {
        str[i]=temp[i];
    }

}

int main()
{
    char word1[1000],word2[1000];
    scanf("%s",word1);
    scanf("%s",word2);
    int a,l=strlen(word1);
    for(int i=0;i<l;i++)
    {
        rotstring(word1);
        a=strcmp(word1,word2);
        if(a==0)
        {
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");



    return 0;

}


Measured memory_bytes: 128
#include <algorithm>
#include <cstdio>

using namespace std;

int S[2010][2010][3];
char p[2010][2010];

int calc(int x1, int y1, int x2, int y2, int ck) {
    return S[x2][y2][ck] - S[x1][y2][ck] - S[x2][y1][ck] + S[x1][y1][ck];
}

int main() {
    int n, m, Q;
    scanf("%d %d %d", &n, &m, &Q);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", p[i] + 1);
        for (int j = 1; j <= m; ++j) {
            S[i][j][0] = p[i][j] - '0';
        }

        for (int j = 1; j < m; ++j) {
            S[i][j][1] = (p[i][j + 1] - '0') * (p[i][j] - '0');
        }

        if (i != 1) {
            for (int j = 1; j <= m; ++j) {
                S[i - 1][j][2] = (p[i][j] - '0') * (p[i - 1][j] - '0');
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int k = 0; k < 3; ++k) {
                S[i][j][k] += S[i - 1][j][k] + S[i][j - 1][k] - S[i - 1][j - 1][k];
            }
        }
    }

    while (Q--) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%d\n", calc(x1 - 1, y1 - 1, x2,     y2,     0) - 
                       calc(x1 - 1, y1 - 1, x2,     y2 - 1, 1) - 
                       calc(x1 - 1, y1 - 1, x2 - 1, y2,     2));
    }
}

Measured memory_bytes: 52864
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
vector<int> x = {1,-1,0,0};
vector<int> y = {0,0,-1,1};
int main(){
    set<ll> data;
    ll n;
    cin >> n;
    rep(i,0,n){
        ll a;
        cin >> a;
        if(data.count(a)){
            data.erase(a);
        }else{
            data.insert(a);
        }
    }
    cout<<data.size()<<endl;

    

  return 0;
}

Measured memory_bytes: 8236
#include <iostream>
using namespace std;
int main(){
  int a[]={5,7,5,7,7},n,i,j,c,k;
  while(cin>>n,n){
    string s[n];
    for(i=0;i<n;i++)cin>>s[i];
    for(i=0;i<n;i++){
      c=k=0;
      for(j=i;j<n;j++){
        c+=s[j].size();
        if(c==a[k]){
          c=0;
          if(++k==5)goto L;
        }
      }
    }
    L:cout<<i+1<<endl;
  }
}

Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define M 1000000007
#define all(a) (a).begin(),(a).end()
#define rep(i,n) reps(i,0,n)
#define reps(i,m,n) for(int i=(m);i<(n);i++)
vector<vector<char>> g(52,vector<char>(52,'#'));
vector<vector<int>> s(52,vector<int>(52,-1));
queue<P> q;
int main(){
  int h,c=0,w;cin>>h>>w;
  reps(i,1,h+1){
    reps(j,1,w+1){
      cin>>g[i][j];
      if(g[i][j]=='#')c++;
    }
  }
  s[1][1]=1;
  q.push(P(1,1));
  while(!q.empty()){
    P p=q.front();
    int ff=p.first,ss=p.second;int m=s[ff][ss];
    q.pop();
    if(g[ff-1][ss]=='.'){
      s[ff-1][ss]=m+1;
      g[ff-1][ss]='#';
      q.push(P(ff-1,ss));
    }
    if(g[ff+1][ss]=='.'){
      s[ff+1][ss]=m+1;
      g[ff+1][ss]='#';
      q.push(P(ff+1,ss));
    }
    if(g[ff][1+ss]=='.'){
      s[ff][1+ss]=m+1;
      g[ff][1+ss]='#';
      q.push(P(ff,1+ss));
    }
    if(g[ff][ss-1]=='.'){
      s[ff][ss-1]=m+1;
      g[ff][ss-1]='#';
      q.push(P(ff,ss-1));
    }
  }
  if(s[h][w]==-1)cout<<-1;
  else cout<<h*w-c-s[h][w];
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

#define PI pair <int, int>
#define f first
#define s second
#define M 200010
#define P 998244353

using namespace std;

typedef long long ll;

map <PI, int> mmp;

int n, m;

PI _1[M], _2[M], _3[M];

ll F[M][2][2];

int Abs(int x) {return x < 0 ? -x : x;}

PI getv(PI S) {
    if(S.f == 0) return PI(S.s == 0, S.s == 1);
    int t = 1;
    S.s--;
    while(S.s--) t *= 2;
    return PI(t, t);
}

ll powmod(ll x, ll y = P - 2, ll p = P) {
    ll ans = 1;
    while(y) {
        if(y & 1) ans = ans * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ans;
}

void add(ll &x, ll y) {x = (x + y) % P;}

void Search(int x, PI _1, PI _2, PI _3) {
    if(_1.f) {
        Search(x, PI(_1.f - 1, _1.s), _2, _3);
        Search(x, PI(_1.f - 1, _1.s ^ 1), _2, _3);
    } else if(_2.f) {
        Search(x, _1, PI(_2.f - 1, _2.s), _3);
        Search(x, _1, PI(_2.f - 1, _2.s ^ 1), _3);
    } else if(_3.f) {
        Search(x, _1, _2, PI(_3.f - 1, _3.s));
        Search(x, _1, _2, PI(_3.f - 1, _3.s ^ 1));
    } else {
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++) {
                int a = _1.s ^ _2.s ^ _3.s ^ i, b = _1.s ^ _2.s ^ j, c = _1.s;
                if(x >= 3 && a) continue;
                if(x >= 2 && b) continue;
                add(F[x][b][c], F[x - 1][i][j]);
            }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) _1[i] = PI(1, 0), _2[i] = PI(2, 0), _3[i] = PI(2, 0);
    _2[1] = (_3[1] = (_3[2] = PI(0, 0)));
    if(n == 2) {
        int s = 0;
        for(int i = 1; i <= m; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            s ^= c;
        }
        if(m == 4 && s == 1) puts("0"); else if(m == 4 && s == 0) puts("1"); else {
            int ans = 1, t = 3 - m;
            while(t--) ans *= 2;
            printf("%d\n", ans);
        }
        return 0;
    }
    ll tot = (ll) (n - 2) * (n - 3) / 2;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if(Abs(a - b) == 0) _1[a].f--, _1[a].s ^= c;
        else if(Abs(a - b) == 1) {
            if(a > b) swap(a, b);
            _2[b].f--, _2[b].s ^= c;
        } else if(Abs(a - b) == 2) {
            if(a > b) swap(a, b);
            _3[b].f--, _3[b].s ^= c;
        } else {
            if(!mmp.count(PI(b, a)) || mmp[PI(b, a)] == c) mmp[PI(a, b)] = c; else return puts("0"), 0;
            if(!mmp.count(PI(b, a))) tot--;
        }
    }
    if(_1[1].f == 1) F[1][0][0] = (F[1][1][1] = 1); else F[1][_1[1].s][_1[1].s] = 1;
    for(int i = 2; i <= n; i++) {
        Search(i, _1[i], _2[i], _3[i]);
    }
    ll ans = (F[n][0][0] + F[n][0][1]) % P;
    printf("%lld\n", ((ans * powmod(2, tot) % P + P) % P));
    return 0;
}

Measured memory_bytes: 11520
n,q = map(int, input().split())
que = []
t = 0
for i in range(n):
    que.append(input().split())

while len(que) != 0:
    proc =  que.pop(0)
    if int(proc[1]) <= q:
        t += int(proc[1])
        print(proc[0],t)
    else:
        t += q
        proc[1] = int(proc[1]) - q
        que.append(proc)

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

using namespace std;


int main(){
  string a,b,c;
  cin >> a >> b >> c;
  if(a.back()==b.front()&&b.back()==c.front()){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
// A.

#include <iostream>
#include <sstream>

using namespace std;

typedef long long LL;

int main(int argc, char *argv[])
{
	string a, b, c;
	cin >> a >> b >> c;
	bool ans = (a.back() == b.front() && b.back() == c.front());
	cout << (ans ? "YES" : "NO") << endl;
	return 0;
}


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

int abc2num(char s){
    if(s == 'a') return 0;
     else if(s == 'b') return 1;
     else if(s == 'c') return 2;
     else if(s == 'd') return 3;
     else if(s == 'e') return 4;
     else if(s == 'f') return 5;
     else if(s == 'g') return 6;
     else if(s == 'h') return 7;
     else if(s == 'i') return 8;
     else if(s == 'j') return 9;
     else if(s == 'k') return 10;
     else if(s == 'l') return 11;
     else if(s == 'm') return 12;
     else if(s == 'n') return 13;
     else if(s == 'o') return 14;
     else if(s == 'p') return 15;
     else if(s == 'q') return 16;
     else if(s == 'r') return 17;
     else if(s == 's') return 18;
     else if(s == 't') return 19;
     else if(s == 'u') return 20;
     else if(s == 'v') return 21;
     else if(s == 'w') return 22;
     else if(s == 'x') return 23;
     else if(s == 'y') return 24;
     else if(s == 'z') return 25;

     return 100;
}

int S[50][26];

int main(){
    int n;
    cin >> n;
    for(int i=0; i < n; i++){
        string s;
        cin >> s;
        for(int j=0; j < (int)s.size(); j++){
            S[i][abc2num(s[j])] += 1;
        }
    }

    int row[26] = {0};
    int nums[26] = {0};
    for(int i=0; i < 26; i++){
        int flag = 0;
        int cnt = 100;
        for(int j=0; j < n; j++){
            if(S[j][i]) flag++;
            cnt = min(cnt, S[j][i]);
        }
        if(flag == n) row[i] = 1;
        nums[i] = cnt;
    }

    //debug
    //for(int i=0; i < 25; i++) cout << row[i] << " " ;
    //for(int i=0; i < 25; i++) cout << nums[i] << " " ;

    //出力用
    string alph[] = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"};
    string ans = "9";
    for(int i=0; i < 26; i++){
        for(int j=0; j < nums[i]; j++){
            if(row[i]) ans += alph[i];
        }
    }

    cout << ans.substr(1, (int)ans.size()) << endl;

    return 0;
}


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

typedef pair<long long int,long long int> P;

int main(){
  int N,a;
  cin >> N;
  set<int> d;
  for(int i=0; i<N; i++){
    cin >> a;
    d.insert(a);
  }
  cout << d.size() << endl;
  return 0;
}

Measured memory_bytes: 256
package main;
import "fmt";
import "math";

func main()  {
	var N,S1,S2,ans int;
	fmt.Scan(&N);
	
	var W = make([]int,N)
	for i:=0;i<N;i++{fmt.Scan(&W[i]);}

	ans = 99999999
	for i:=0;i<N;i++{
		for j:=0;j<i;j++{S1 += W[j]}
		for k:=i;k<N;k++{S2 += W[k]}
		ans = int(math.Min(math.Abs(float64(S1-S2)),float64(ans)))

		S1 = 0;S2 = 0;
	}
	fmt.Println(ans);	
}

Measured memory_bytes: 512
program main
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: n, ni

    read*, n
    ni = mod(n,10)

    if (ni==3) then
        print'(a)', 'bon'
    else if (ni==0 .or. ni==1 .or. ni==6 .or. ni==8) then
        print'(a)', 'pon'
    else
        print'(a)', 'hon'
    end if
end program main

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

int main(){
    int a[5];
    int b[5];
    
    for(int i=0; i<5; i++){
    cin >> a[i];
    }
    int k = 10;
    int m = 0;
    int n = 0;
    for(int i=0; i<5; i++){
       n = a[i] % 10;
       if(n<k && n != 0){
         m = i;
         k = n;
       }
      
       if(n != 0) {
         n = 10 - n;
       }
       b[i] = a[i] + n;
    }
    int sum = 0;
    for(int i = 0; i < 5; i++){
        sum += b[i];
      
    }
    sum -= b[m];
    sum += a[m];
    cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<cmath>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>
    #include<cassert>
    #include<cmath>
    #include<cstdint>
    #include<numeric>
    #include<array>
     
    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
    #define ALL(a)  (a).begin(),(a).end()
    #define chmin(a, b) a = min(a, b)
    #define chmax(a, b) a = max(a, b)
    #define Vl vector<ll>
     
    using namespace std;
    using ll = long long;
    using Graph = vector<vector<int>>;
    using P = pair<ll, ll>;
     
const ll MOD = 1e9 + 7;
const ll ZER = 0;


int main(){
   int n;
   cin >> n;
   if(n == 1)cout << 0 << endl;
   else cout << 1 << endl;
}


Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

int main() {
    ll n;   cin >> n;
    vector<ll> x(n), y(n);
    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];

    vector<ll> p, q, r, s;
    for (int i = 0; i < n; i++) {
        p.push_back(x[i] + y[i]);
        q.push_back(x[i] - y[i]);
        r.push_back(-x[i] + y[i]);
        s.push_back(-x[i] - y[i]);
    }
    sort(p.begin(), p.end(), greater<ll>());
    sort(q.begin(), q.end(), greater<ll>());
    sort(r.begin(), r.end(), greater<ll>());
    sort(s.begin(), s.end(), greater<ll>());
   

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll a = x[i], b = y[i];
        ll c = p[0] - a - b;
        ll d = q[0] - a + b;
        ll e = r[0] + a - b;
        ll f = s[0] + a + b;
        ans = max(ans, max(max(c, d), max(e, f)));
    }

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

Measured memory_bytes: 12888
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
var n=Arr.shift()-0;
var arr=Arr.shift().split("");
var cnt=0;
for(var i=0;i<n;i++){
   var str=Arr.shift();
   var a="";
   while(true){
      var s=arr.join(a);
      if(s.length>=100)break;
      var re = new RegExp(s);
      if(re.test(str)){cnt++;break;}
      a+=".";
   }
}
console.log(cnt);

Measured memory_bytes: 9800
a,b,c=map(int, input().split())
if a < b < c :
    print(a,b,c)
elif a < c < b :
    print(a,c,b)
elif b < a < c :
    print(b,a,c)
elif b < c < a :
    print(b,c,a)
elif c < a < b :
    print(c,a,b)
elif c < b < a :
    print(c,b,a)
elif a == b < c :
    print(a,b,c)
elif a == b > c :
    print(c,a,b)
elif b == c < a :
    print(b,c,a)
elif b == c > a :
    print(a,b,c)
elif a == c < b :
    print(a,c,b)
elif a == c > b :
    print(b,a,c)
elif a == b == c :
    print(a,b,c)
else :
    pass


Measured memory_bytes: 5608
#include <stdio.h>

int main(void)
{
    char s[4], t[4];
    int i, count = 0;

    scanf("%s %s", &s, &t);
    for (i = 0; i < 3; i++)
    {
        if (s[i] == t[i]) count++;
    }

    printf("%d\n", count);

    return 0;
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 28;

int n, m, s, g1, g2;
int dist[100][100];

int main()
{
	while (scanf("%d %d %d %d %d", &n, &m, &s, &g1, &g2), n){
		--s; --g1; --g2;
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				dist[i][j] = INF;
			}
			dist[i][i] = 0;
		}
		for (int i = 0; i < m; i++){
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			dist[--a][--b] = c;
			//dist[  b][  a] = c;
		}
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				for (int k = 0; k < n; k++){
					dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
				}
			}
		}
		int res = INF;
		for (int c = 0; c < n; c++){
			int t = dist[s][c] + dist[c][g1] + dist[c][g2];
			res = min(res, t);
		}
		printf("%d\n", res);
	}
}

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

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

struct Seg {
    vector <int> seg, lazy;
    Seg (int n) {
        seg.resize (4 * n + 1, n + 1);
        lazy.resize (4 * n + 1, n + 1);
    }
    void push (int x) {
        int l = x * 2;
        int r = x * 2 + 1;
        seg[l] = min (seg[l], lazy[x]);
        seg[r] = min (seg[r], lazy[x]);
        lazy[l] = min (lazy[l], lazy[x]);
        lazy[r] = min (lazy[r], lazy[x]);
        lazy[x] = (1 << 30);
    }
    void updateRange (int node, int lb, int rb, int ql, int qr, int val) {
        if (ql <= lb && rb <= qr) {
            seg[node] = min (seg[node], val);
            lazy[node] = min (lazy[node], val);
            return;
        }
        push (node);
        int mid = (lb + rb) / 2;
        if (ql <= mid)
            updateRange (node * 2, lb, mid, ql, qr, val);
        if (qr >= mid + 1)
            updateRange (node * 2 + 1, mid + 1, rb, ql, qr, val);
    }
    int queryPos (int node, int lb, int rb, int pos) {
        if (lb == rb)
            return seg[node];
        push (node);
        int mid = (lb + rb) / 2;
        if (pos <= mid)
            return queryPos (node * 2, lb, mid, pos);
        else
            return queryPos (node * 2 + 1, mid + 1, rb, pos);
    }
};
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, q;
    cin >> n >> q;
    n -= 2;
    Seg L (n), C (n);
    ll black = 1ll * n * n;
    while (q--) {
        int type, x;
        cin >> type >> x; x--;
        if (type == 1) {
            int to = C.queryPos (1, 1, n, x) - 1;
            black -= to;
            C.updateRange (1, 1, n, x, x, 1);
            if (to)
                L.updateRange (1, 1, n, 1, to, x);
        }
        else {
            int to = L.queryPos (1, 1, n, x) - 1;
            black -= to;
            L.updateRange (1, 1, n, x, x, 1);
            if (to)
                C.updateRange (1, 1, n, 1, to, x);
        }
    }
    cout << black << "\n";
    return 0;
}


Measured memory_bytes: 15876
#include "bits/stdc++.h"
using namespace std;
vector<int> h;
vector<long long> c;
int n;
int lowbit(int x)
{
    return x&-x;
}
void update(int index,long long maxv)
{
    while(index<=n)
    {
	c[index]=max(maxv,c[index]);
	index+=lowbit(index);
    }
}
long long maxrange(int index)
{
    long long ret=0;
    while(index)
    {
	ret=max(ret,c[index]);
	index-=lowbit(index);
    }
    return ret;
}
int main()
{
    int a;
    int i;
    long long ans,t;
    scanf("%d",&n);
    h.resize(n);
    c.resize(n+1);
    for(i=0;i<n;i++)
    {
	scanf("%d",&h[i]);
    }
    for(i=0;i<n;i++)
    {
	scanf("%d",&a);
	t=maxrange(h[i]-1);
	ans=max(ans,t+a);
        update(h[i],t+a);
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 2560
<?php
$n = trim(fgets(STDIN));
for($i=0;$i<$n;$i++){
    $out_count=0;
    $run_count=0;
    $point=0;
    while($out_count<3){
        $event=trim(fgets(STDIN));
        if($event=='OUT'){
            $out_count++;
        }else if($event=='HIT'){
            if($run_count==3){
                $point++;
                continue;
            }
            $run_count++;
        }else{
            $point+=$run_count+1;
            $run_count=0;
        }
    }
    echo $point . "\n";
}

Measured memory_bytes: 15092
#include <bits/stdc++.h>
using namespace std;
#include "string"
#define endl '\n'
#define PI pair<int,int>
#define ff first
#define ss second
#define int long long 
#define boost ios_base::sync_with_stdio(false);cin.tie(nullptr)


int32_t main() { 
    boost;
    
    int n;
    cin>>n;
    int ans = 1000*(n/500);
    n%=500;
    ans+=5*(n/5);
    cout<<ans<<endl;
}	

Measured memory_bytes: 256
using System;

namespace AtCorder
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(' ');
            var a = int.Parse(inputs[0]);
            var b = int.Parse(inputs[1]);

            var answer = (a - (2 * b)) > 0 ? (a - (2 * b)) : 0;

            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 11092
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
  ll n, m;
  cin >> n >> m;
  ll a = 1000000007, ans = 1, elseAns = 1;
  for (ll i = 2; i <= max(n, m); i++) {
    ans = ans * i % a;
  }
  if (n == m) ans = ans * ans % a * 2 % a;
  else if (abs(n - m) == 1) {
    for (ll i = 2; i <= min(n, m); i++) elseAns = elseAns * i % a;
    ans = ans * elseAns % a;
  } else ans = 0;
  cout << ans << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-5)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H &b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H &b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H &b) const { return x == b.x&&y == b.y; }
	bool operator!=(const H &b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P &b) const { return cost < b.cost; }
	bool operator>(const P &b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E &b) const { return cost < b.cost; }
	bool operator>(const E &b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T &a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T &a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j%i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
vector<string>split(string s, char c = ' ') {
	vector<string>vec;
	string h = "";
	for (int i = 0; i < s.size();) {
		int j = i;
		while (j < s.size() && s[j] != ' ') {
			h += s[j++];
		}
		if (h.size() > 0) vec.push_back(h);
		h = "";
		i = j + 1;
	}
	return vec;
}
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
struct A {
	int w, s, v;
};
bool operator<(A a, A b) {
	return a.s + a.w < b.s + b.w;
}
int n;
A a[2000];
int dp[30000];
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i].w >> a[i].s >> a[i].v;
	}
	sort(a, a + n);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = a[i].s; j >= 0; j--) {
			dp[j + a[i].w] = max(dp[j + a[i].w], dp[j] + a[i].v);
			ans = max(ans, dp[j + a[i].w]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
S = [ord(s) - 97 for s in input()]
T = [ord(t) - 97 for t in input()]
SS = S + S
ls = len(S)

indexes = [[] for _ in range(26)]
for i, s in enumerate(SS):
    indexes[s].append(i)
m = [[-1] * 26 for _ in range(2 * ls)]
for s in range(26):
    inds = [0] + indexes[s]
    for r in range(1, len(inds)):
        for i in range(inds[r-1], inds[r]):
            m[i][s] = inds[r] - i

ans = 0
i = ls - 1
for t in T:
    cnt = m[i][t]
    if cnt == -1:
        print(-1)
        exit()
    ans += cnt
    i = (i + cnt) % ls
print(ans)


Measured memory_bytes: 112068
#!/usr/bin/env python3


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [tuple(map(typ, input().split())) if m > 1 else typ(input()) for _ in range(n)]


def main():
    W, H, N = read_h()
    pts = read_v(N, m=3)
    area = [[0, 0], [W, H]]

    for x, y, a in pts:
        if a == 1 and area[0][0] < x:
            area[0][0] = x
        elif a == 2 and area[1][0] > x:
            area[1][0] = x
        elif a == 3 and area[0][1] < y:
            area[0][1] = y
        elif a == 4 and area[1][1] > y:
            area[1][1] = y

        if area[1][0] - area[0][0] <= 0 or area[1][1] - area[0][1] <= 0:
            print(0)
            return

    ans = (area[1][0] - area[0][0]) * (area[1][1] - area[0][1])
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
const ll mod=1e9+7;

ll power(ll x,ll n){
  if(n==0) return 1;
  ll res=power(x*x%mod,n/2);
  if(n&1) res=res*x%mod;
  return res;
}

int main(){
  int n;
  cin>>n;
  ll a[n+1];
  a[0]=1;
  rep(i,1,n+1) a[i]=a[i-1]*i%mod;
  ll b[n+1];
  b[n]=power(a[n],1e9+5);
  for(int i=n-1;i>=0;i--) b[i]=b[i+1]*(i+1)%mod;
  ll ans=0;
  int k=1;
  while(n-3*k>=0){
    ans+=a[n-3*k+k-1]*b[k-1]%mod*b[n-3*k]%mod;
    ans%=mod;
    k++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3656
s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力

Measured memory_bytes: 68612