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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for(long long int i=0;i<c;++i)
int  main(){
int a;
cin >> a;
string s,k;
cin >> s>>k;
for(int i = 0;i<a;i++){
  cout << s[i] << k[i];
}
cout << endl;
return 0;
}

Measured memory_bytes: 256
n = int(input())
s = str(input())

def z_algorithm(s):
    n = len(s)
    Z = [0]*n
    Z[0] = n
    i = 1
    j = 0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < n and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

ans = 0
for i in range(n):
    t = s[i:]
    z = z_algorithm(t)
    for j in range(len(z)):
        if z[j] <= j:
            ans = max(ans, z[j])
print(ans)


Measured memory_bytes: 75940
n,m,k=map(int,input().split())
a=[0]*n
b=[0]*m
a=list(map(int,input().split()))
b=list(map(int,input().split()))

ans=0
flag=0
a_now=-1
b_now=m-1
num_a=0
num_b=sum(b)

while b_now>=-1 and a_now<n:
    if (num_a+num_b<=k):
        ans=max(ans,a_now+b_now+2)
        a_now+=1
        if (a_now==n):
          break
        num_a+=a[a_now]
    else:
        b_now-=1
        if (b_now==-2):
          break
        if (b_now==-1):
          num_b=0
        else:
          num_b-=b[b_now+1]
    
print(ans)

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

int main() {
    int N;
    cin>>N;
    cout<<(N-2)*180<<endl;
return 0;}
/*compile
g++ code.cpp
./a.out
run*/

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

#define M_PI 3.14159265358979323846264338327950288
using namespace std;

typedef long double LD;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

LL cs2(LL k) {
    if (k < 2) return 0;
    else return k * (k-1) / 2;
}

int main() {
#ifdef LOCAL_PROJECT
    freopen("input.txt", "r", stdin);
#endif
    string S;
    cin >> S;
    vector<int> C (26, 0);
    for(char c : S) C[c-'a']++;
    LL res = cs2(S.size()) + 1;
    for(int i = 0; i < 26; i++) res -= cs2(C[i]);
    cout << res << endl;
    return 0;
}


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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

Int INF = 1e18;
Int mod = 1e9+7;
//Int mod = 998244353;

int main() {
    Int n;
    cin >> n;
    vector<string> v(n);
    for (Int i = 0; i < n; i++) {
        cin >> v[i];
    }
    map<string, Int> mp;
    for (Int i = 0; i < n; i++) {
        mp[v[i]]++;
    }
    Int ma = -1;
    for (auto i : mp) {
        if (ma < i.se) {
            ma = i.se;
        }
    }
    vector<string> res;
    for (auto i : mp) {
        if (i.se == ma) {
            res.push_back(i.fi);
        }
    }
    sort(all(res));
    for (Int i = 0; i < (Int)res.size(); i++) {
        dump(res[i]);
    }
    return 0;
}


Measured memory_bytes: 28404
#include<cstdio>
using namespace std;
char map[8][8];
void solve(int y,int x);
int main(){
    int n;
    scanf("%d\n",&n);
    for(int i=0;i<n;i++){
        int s_x,s_y;
        for(int j=0;j<8;j++){
            scanf("%s",map[j]);
        }
        scanf("%d\n%d",&s_x,&s_y);
        printf("Data %d:\n",i+1);
        solve(s_y-1,s_x-1);

        for(int j=0;j<8;j++){
            for(int k=0;k<8;k++){
                printf("%c",map[j][k]);
            }
            puts("");
        }

    }
    return 0;
}


void solve(int y,int x){
    
    if(y<-1 || y>7)return;
    if(x<-1 || x>7)return;
    if(map[y][x]=='1'){

        map[y][x]='0';
        for(int i=-3;i<4;i++){
            if(i==0)continue;
            solve(y+i,x);
        }
        for(int i=-3;i<4;i++){
            if(i==0)continue;
            solve(y,x+i);
        }
    }
    return;
}

Measured memory_bytes: 1040
#include<stdio.h>
int main()
{
		int a,z=0,y;
		scanf("%d%d",&a,&y);
		if(a>12)
				printf("%d\n",y);
		else if(a>=6&&a<=12)
				printf("%d\n",y/2);
			else if(a>=0&&a<=5)
				printf("%d\n",z);
				return 0;
}

Measured memory_bytes: 128
M = int(input())
D = [];C = []
S = 0
ans = -1
for i in range(M):
  d,c = map(int,input().split())
  D.append(d);C.append(c)
  S += d*c
  ans += c
kaisu = (S-1)//9
#print(ans,kaisu)
ans += kaisu
print(ans)


Measured memory_bytes: 18464
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int maxN = 1e5 + 55;

struct Segment {
    int l, r;   ll w;

    bool operator < (const Segment &other) const {
        return r < other.r;
    }

    Segment(){};
    Segment(int _l, int _r, ll _w) : l(_l), r(_r), w(_w) {};
};

ll segTree[4 * maxN], lazy[4 * maxN];
int n, m;
Segment a[maxN];

void propagate(int id, int l, int r){
    segTree[id] = min(segTree[id], lazy[id]);

    if(l != r){
        lazy[id * 2] = min(lazy[id * 2], lazy[id]);
        lazy[id * 2 + 1] = min(lazy[id * 2 + 1], lazy[id]);
    }

    lazy[id] = INF;
}

void upd(int id, int l, int r, int L, int R, ll val){
    propagate(id, l, r);
    if(L <= l && r <= R){
        lazy[id] = min(lazy[id], val);
        propagate(id, l, r);
        return;
    }

    if(r < L || l > R){
        return;
    }

    int mid = (l + r) / 2;
    upd(id * 2, l, mid, L, R, val);
    upd(id * 2 + 1, mid + 1, r, L, R, val);

    segTree[id] = min(segTree[id * 2], segTree[id * 2 + 1]);
}

ll getMn(int id, int l, int r, int L, int R){
    propagate(id, l, r);
    if(L <= l && r <= R){
        return segTree[id];
    }

    if(r < L || l > R){
        return INF;
    }
	
		int mid = (l + r) / 2;
		ll ans = getMn(id * 2, l, mid, L, R);
		ans = min(ans, getMn(id * 2 + 1, mid + 1, r, L, R));

		return ans;
}

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

    cin >> n >> m;

    for(int i = 0; i < m; i++){
        int l, r;   ll w;   cin >> l >> r >> w;
        a[i] = Segment(l, r, w);
    }

    sort(a, a + m);

    for(int i = 0; i < 4 * maxN; i++){
        segTree[i] = lazy[i] = INF;
    }

    upd(1, 1, n, 1, 1, 0);
    for(int i = 0; i < m; i++){
        ll mn = getMn(1, 1, n, a[i].l, a[i].r);
				upd(1, 1, n, a[i].l, a[i].r, a[i].w + mn);
    }

		ll fRes = getMn(1, 1, n, n, n);

		if(fRes >= INF){
			cout << "-1\n";
			return 0;
		}

		cout << fRes << '\n';

    return 0;
}

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

int main(){
  int N, K, Q;
  cin >> N >> K >> Q;
  int A[Q];
  for(int i = 0; i < Q; i++){
    cin >> A[i];
  }
  int S[N] = {0};
  for(int i = 0; i < Q; i++){
    S[A[i] - 1]++;
  }
  for(int i = 0; i < N; i++){
    if(K - Q + S[i] > 0){
      cout << "Yes" << '\n';
    }
    else{
      cout << "No" << '\n';
    }
  }
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  double d;
  cin >> n >> d;
  int ans = 0;
  while (n--) {
    double x, y;
    cin >> x >> y;
    if (hypot(x, y) <= d) {
      ans++;
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3836
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
typedef pair<int, int> P;
double dp[3000][3000]; //dp[i]::=i番目までのコインをなげたとき表がj枚出る確率
double p[3000];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> p[i];
	}
	dp[0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			dp[i + 1][j + 1] += dp[i][j] * p[i];
			dp[i + 1][j] += dp[i][j] * (1 - p[i]);
		}
	}
	double ans = 0;
	for (int i = N; i >= (N + 1) / 2; i--) ans += dp[N][i];
	printf("%.15lf\n", ans);
}


Measured memory_bytes: 68992
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll n;
    cin>>n;
    ll c=n;
    for(ll i=10;i<=n;i*=100) c-=min(n-i+1,i*9);
    cout<<c<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<functional>
#include<map>
#include<unordered_set>
using namespace std;
/*int p = 998244353;*/
int p = 1000000007;
#define int long long
#define vel vector<long long>
#define vvel vector<vel>
#define rep(i,n) for(int i=0;i<n;i++)
#define sor(v) sort(v.begin(),v.end())
#define mmax(a,b) a=max(a,b)
#define mmin(a,b) a=min(a,b)
#define mkp make_pair
#define pin pair<int,int>
#define qin pair<int,pin>
#define V vector
#define Endl endl
#define veb vector<bool>
#define rev(s) reverse(s.begin(),s.end())
signed main() {
	int h, n; cin >> h >> n;
	if (h == 1) { cout << 0 << endl; return 0; }
	vvel dp(h, vel(16, 0));
	vvel nex = { {0},{12,6,3},{15} };
	vel sta(h, 0);
	rep(i, n) {
		int x, y; cin >> x >> y;
		sta[y] += (1 << x);
	}
	for (int i = 0; i < h - 1; i++) {
		for (int j = 0; j < 16; j++) {
			if ((sta[i] & j) == 0) {
				int qsta = sta[i] ^ j;
				for (int k = 0; k < 3; k++) {
					for (auto x : nex[k]) {
						if ((qsta&x) == 0) {
							mmax(dp[i + 1][x], dp[i][j] + k);
						}
					}
				}
			}
		}
	}
	int ans = 0;
	for (int j = 0; j < 16; j++) {
		if ((sta[h-1] & j) == 0) {
			mmax(ans, dp[h - 1][j]);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4768
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

int main() {
  string S;
  cin >> S;
  for (int i = 0; i < S.size(); ++i) {
    cout << "x";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include <unistd.h>

void create_map_base(char *map, int x, int y)
{       
       	int i;
        int j;
        
        j = -1;
        while (++j < y)
        {       
                i = -1;
                while (++i < x) 
                        map[j * x + i] = '.';
        }
}

void create_map(char *map, int x, int y)
{
        int i;
        int j;
   		char a[x];
  
        j = 0;
        while (++j < y + 1)
        {      
                read(0, a, x);
                i = 0;
                while (++i < x + 1)
                        map[j * (x + 2) + i] = a[i - 1];
          		if (j != y)
                  		read(0, a, 1);
        } 
}

int count_num(char *map, int x, int i, int j)
{
		int count;
  
  		count = 0;
        if (map[(j - 1) * (x + 2) + (i - 1)] == '#')
                count++;
        if (map[(j - 1) * (x + 2) + i] == '#')
                count++;
        if (map[(j - 1) * (x + 2) + (i + 1)] == '#')
                count++;
        if (map[j * (x + 2) + (i - 1)] == '#')
                count++;
        if (map[j * (x + 2) + (i + 1)] == '#')
                count++;
        if (map[(j + 1) * (x + 2) + (i - 1)] == '#')
                count++;
        if (map[(j + 1) * (x + 2) + i] == '#')
                count++;
        if (map[(j + 1) * (x + 2) + (i + 1)] == '#')
                count++;
  		return (count);
}

void write_num(char *map, int x, int y)
{
        int i;
        int j;
  		char count;
  
        j = 0;
        while (++j < y + 1)
        {
                i = 0;
                while (++i < x + 1)
                {
        				if (map[j * (x + 2) + i] == '.')
                        {
                  				count = count_num(map, x, i, j) + '0';        		
                          		write(1, &count, 1);
                        }
                		else
                				write(1, "#", 1);
                }
                write(1, "\n", 1);
        }
}

void maping(int x, int y)
{

        char map[y + 2][x + 2];
  
        create_map_base(&map[0][0], x + 2, y + 2);
        create_map(&map[0][0], x, y);
        write_num(&map[0][0], x, y);
}


int main()
{
        int x[2];
  		char c;
  		int count;
  		int num;

  		count = 0;
		c = 0;
  		while (c != 10)
        {
  			if (read(0, &c, 1) == -1)
          		return (0);
            if (c != 32)
            {
              	num = 0;
              	while (c != 10 && c != 32)
                {
             			num = num * 10 + c - '0';
                  		if (read(0, &c, 1) == -1)
          						return (0);
                }
              	x[count++] = num;
            }
        }
        maping(x[1], x[0]);
        return (0);
}


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

int main(void) {
    int x1,y1,x2,y2;
    int tx,ty,tmp;
    int x3,y3,x4,y4;
    cin >> x1 >> y1 >> x2 >> y2;

    // x2y2を中心としてx1y1を90度時計回りに移動させる
    tx = x1 - x2;
    ty = y1 - y2;
    // x = xcos270 - ysin270
    // y = xsin270 + ycos270
    tmp = tx;
    tx = ty;
    ty = -tmp;
    x3 = tx + x2;
    y3 = ty + y2;

    // x3y3を中心としてx2y2を90度時計回りに移動させる
    tx = x2 - x3;
    ty = y2 - y3;
    tmp = tx;
    tx = ty;
    ty = -tmp;
    x4 = tx + x3;
    y4 = ty + y3;
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;

    return 0;
}


Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

def calc_(x,n):
    ans = 0
    for i in range(n-1):
        ans += x[i] - 1
        ans *= (n-1-i)
        for j in range(i+1 , n):
            if(x[j] > x[i]):
                x[j] -= 1
    return ans

print( abs(calc_(p,n) - calc_(q,n)))

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

int main() {
    string s;
    cin >> s;
    int n= s.size();
for(int i=0;i<n;i++){
    if(!(s[i]==s[n-1-i])){cout << "No";
    return 0;}
}
for(int i=0;i<(n-1)/2;i++){
    if(!(s[i]==s[(n-1)/2-i-1])){cout << "No";
    return 0;}
}
for(int i=(n+1)/2;i<n;i++){
    if(!(s[i]==s[n-1+((n+1)/2)-i])){cout << "No";
    return 0;}
}
cout << "Yes";
}


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

using namespace std;

#define fo(i,n) for(int i=0; i<n; i++)
#define Fo(i,k,n) for(int i=k; i<n; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, a) for(auto it=a.begin(); it!=a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

int H,W;
vvi dp;
vector<vector<char>> grid;

ll modV = 1e9+7;

void mod(int &a, int b){
    if(modV-a <= b){
        a += (b-modV);
    }else{
        a += b;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);

    cin>>H>>W;
    dp.resize(H+1, vi(W+1, 0));
    grid.resize(H+1, vector<char>(W+1));
    fo(i,H)
        fo(j,W){
            cin>>grid[i+1][j+1];
        }
    dp[1][1] = 1;
    Fo(i,1,H+1){
        Fo(j,1,W+1){
            if((j<W) && (grid[i][j+1] != '#'))mod(dp[i][j+1], dp[i][j]);
            if((i<H) && (grid[i+1][j] != '#'))mod(dp[i+1][j], dp[i][j]);
        }
    }
    cout<<dp[H][W]<<endl;
    
    return 0;
}

Measured memory_bytes: 5248
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
ll pow(ll a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }



int main() {
    
    int n, m;
    cin >> n >> m;
    priority_queue<int> q;
    rep(i, n) {
        int a;
        cin >> a;
        q.push(a);
    }
    rep(i, m) {
        int now = q.top();
        q.pop();
        // cout << now << endl;
        now /= 2;
        q.push(now);
    }
    ll ans = 0;
    rep(i, n) {
        // cout << q.top() << endl;
        ans += q.top();
        q.pop();
    }
    cout << ans << endl;
}


Measured memory_bytes: 892
#include <iostream>
#include <math.h>
using namespace std;
int main() {
long long int A,B,C,D,N;
cin>>A>>B>>C>>D;
cin>>N;
long long int k;
k=fmin(A*4,B*2);
k=fmin(k,C);

if(k*2>D){
  cout<<(N/2)*D+(N%2)*k;
}
else{
  cout<<N*k;
  }
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    P = [int(input()) for _ in range(N)]

    p2idx = {x: i for i, x in enumerate(P)}

    # 数が連続する増加部分数列の最大の長さを調べる
    # ある数字pが右端となる時の部分数列の最大の長さを保持
    max_len = 1
    tmp = 1
    for p in range(2, N + 1):
        if p2idx[p] > p2idx[p - 1]:
            tmp += 1
            if max_len < tmp:
                max_len = tmp
        else:
            tmp = 1

    print(N - max_len)

if __name__ == "__main__":
    main()

Measured memory_bytes: 35008
# string
# a, b, c = input().split()
# str_list = list(input().split())

# number
# a, b, c = map(int, input().split())
# num_list = list(map(int, input().split()))

# lows
# str_list = [input() for _ in range(n)]

# many inputs
# num_list = []
# for i in range(n): num_list.append(list(map(int, input().split())))

n, x, t = map(int, input().split())

a = int((n+x-1)/x)
print(t*a)

Measured memory_bytes: 9152
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////


int main() {

	ll a, b;
	cin >> a >> b;

	ll n;

	if (b < 10) { n = 10 * a + b; }
	else if (b < 100) { n = 100 * a + b; }
	else { n = 1000 * a + b; }

	string ans = "No";

	for (int i = 1; i*i <= n; i++) {
		if (i*i == n) { ans = "Yes"; }
	}

	cout << ans;

	system("PAUSE");

	

}


Measured memory_bytes: 504
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main()
{
  long long N;
  scanf("%lld", &N);
  long long A;
  scanf("%lld", &A);
  long long B;
  scanf("%lld", &B);
  std::vector<long long> X(N);
  for (int i = 0; i < N; i++)
  {
    scanf("%lld", &X[i]);
  }
  ll ans = 0;
  for (int i = 0; i < N - 1; ++i)
  {
    ans += min(A * (X[i + 1] - X[i]), B);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
def main():
    import sys
    input = sys.stdin.readline

    a, b, c, d, e, f = map(int, input().split())

    dp = [[False] * (f+1) for _ in range(f+1)]
    dp[0][0] = True
    for i in range(f+1):
        for j in range(f+1):
            if dp[i][j]:
                if i + 100*a <= f:
                    dp[i+100*a][j] = True
                    if i + 100*b <= f:
                        dp[i+100*b][j] = True
                if j + c <= f and i+c <= f:
                    if ((i - j) / 100) * e >= (j+c):
                        dp[i+c][j+c] = True
                        if j + d <= f and i+d <= f:
                            if ((i - j) / 100) * e >= (j+d):
                                dp[i+d][j+d] = True

    M = 0
    sugar = 0
    con = -1
    for i in range(1, f+1):
        for j in range(f, -1, -1):
            if dp[i][j]:
                if j / i > con:
                    M = i
                    sugar = j
                    con = j/i
                break
    print(M, sugar)

if __name__ == '__main__':
    main()


Measured memory_bytes: 106076
import java.util.Scanner;

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

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

        System.out.println("-1 -1 -1");
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793

int main(){
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    cout << (s == "abc" ? "Yes":"No") << endl;
}


Measured memory_bytes: 256
A, B, N =map(int, input().split())
"""直感的にはAxがちょうどBの倍数になった時　or　超えた時が大きくなりそう？それだけで探索する
ほとんどは同じ値になる A,Bの値が小さくNがでかい時、死ぬ
xの増加による挙動は 4パターンしかない
不等式から最大値は高々Aであるとわかる　それで探索する？"""
"""解説：
f (x) = f loor(Ax/B) − A × f loor(x/B) とします。
f(x + B) = f(x) であることは実際に代入することで容易に分かります。なので、0 ≤ x ≤ B − 1 の場合のみを考えます。
このとき、f (x) = f loor(Ax/B) − A × f loor(x/B) = f loor(Ax/B) で、f loor(Ax/B) は広義単 調増加なので、与えられた制約 (0 ≤ x ≤ B − 1, 0 ≤ x ≤ N) の中で最も大きい x について、f(x) が求める最大値です。
よって、答えは f (min(B − 1, N )) です。
単純に数学的事実を使うだけの問題"""

a = min(B-1,N)
print(int(A*a/B))


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

int t, d, l;
vector<int> x;

int solve();

int main() {
  while(1) {
    cin >> t >> d >> l;
    if(t + d + l == 0) break;
    x.assign(t, 0);
    for(int i = 0; i < t; ++i) cin >> x[i];
    cout << solve() << endl;
  }

  return 0;
}

int solve() {
  int ans = 0, lim = -1;
  for(int i = 0; i < t; ++i) {
    if(lim >= i) ++ans;
    if(x[i] >= l) lim = i + d;
  }
  return ans;
}


Measured memory_bytes: 3540
#include<iostream>
using namespace std;
int main(){
	string s;
	cin >> s;
	char c[26]={};
	bool ans=true;
	for(int i=0;i<s.length();i++){
		c[s[i]-'a']++;
		if(c[s[i]-'a']>1) ans=false;
	}
	if(ans) cout << "yes" << endl;
	else cout << "no" << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
int main() {
	while (1) {
		int D, N; cin >> D >> N;
		if (!D)break;
		vector<int>as, es, rs;
		for (int i = 0; i < N; ++i) {
			int a, e, r; cin >> a >>e >> r;
			as.push_back(a);
			es.push_back(e);
			rs.push_back(r);

		}
		int dp[101][101];
		for (int i = 0; i < 101; ++i) {
			for (int j = 0; j < 101; ++j) {
				dp[i][j] = 1000;
			}
		}
		dp[0][0] = 0;
		for (int d = 0; d < D; ++d) {
			for (int e = 0; e <= 100; ++e) {
				for (int i = 0; i < N; ++i) {
					if (e >= rs[i]) {
						const int nexte = min(100, e + es[i]);
						const int nextd = min(D, d + as[i]);
						dp[nextd][nexte] = min(dp[nextd][nexte], dp[d][e] + 1);
					}
				}
			}
		}
		int ans = 1000;
		for (int d = D; d <= D; ++d) {
			for (int e = 0; e <= 100; ++e) {
				ans = min(ans, dp[d][e]);
			}
		}
		if (ans == 1000)cout << "NA" << endl;
		else cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3172
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define FOR(idx, begin, end) for(int idx = (int)(begin); idx < (int)(end); ++idx)

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

using namespace std;
typedef long long lint;

const int MOD = 1000000007, INF = 1111111111;
const double EPS = 1e-9;

class Combi {
private:
	vector<lint> fac, inv, finv;

public:
	vector<vector<lint>> Ctb;
	void tbinit(int N = 2000) {
		Ctb.resize(N + 1, vector<lint>(N + 1));
		for (int i = 0; i <= N; i++) {
			Ctb[i][0] = 1;
			Ctb[i][i] = 1;
		}
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k < j; k++) {
				Ctb[j][k] = (Ctb[j - 1][k - 1] + Ctb[j - 1][k]) % MOD;
			}
		}
	}

	void init(int N = 100000) {
		fac.resize(N); inv.resize(N); finv.resize(N);
		fac[0] = fac[1] = 1; inv[1] = 1; finv[0] = finv[1] = 1;

		for (int i = 2; i < N; i++) {
			fac[i] = fac[i - 1] * i % MOD;
			inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
			finv[i] = finv[i - 1] * inv[i] % MOD;
		}
	}

	lint Cmod(int n, int k) {
		if (n < k) return 0;
		if (n < 0 || k < 0) return 0;
		return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
	}
};

int main() {

	cin.tie(0);

	int H, W, A, B;
	cin >> H >> W >> A >> B;

	lint ans = 0;
	Combi combi;
	combi.init(H+W-2);

	FOR(i, 1, H - A + 1) {
	
		ans += combi.Cmod(B + i - 2, i - 1) * combi.Cmod(H - i + W - B - 1, W - B - 1) % MOD;
		ans %= MOD;
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 4992
# frozen_string_literal: true

def select_index(str, substr)
  i = 0
  indexs = []
  loop do
    index = str.index(substr, i)
    return indexs unless index

    indexs << index
    i = index + 1
  end

  indexs
end

n, m = gets.split(' ').map!(&:to_i)

a = []
b = []
n.times { a << gets.chomp! }
m.times { b << gets.chomp! }

ans = 'No'

first_line = b.shift
a.each.with_index do |a_s, i|
  select_index(a_s, first_line).each do |index|
    match = true
    b.each.with_index(1) do |b_s, j|
      if a[i + j].nil? || b_s != a[i + j].slice(index, m)
        match = false
        break
      end
    end
    if match
      ans = 'Yes'
      break
    end
  end
  break if ans == 'Yes'
end

puts ans


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

struct node {
	bool is_end;
	node *go[26];

	node(): is_end(0) { memset(go,0,sizeof go); }
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n; cin >> n;
	vector<string> a(n);
	FOR(i,0,n) {
		cin >> a[i];
		reverse(all(a[i]));
	}
	
	node *root = new node();
	
	for (string s: a) {
		node *cur = root;
		for (char c: s) {
			if (!cur->go[c-'a']) {
				cur->go[c-'a'] = new node();
			}
			cur = cur->go[c-'a'];
		}
		cur->is_end = 1;
	}
	
	ll res = 0;
	for (string s: a) {
		vl last_occ(26,-1);
		FOR(i,0,sz(s)) last_occ[s[i]-'a'] = i;
		
		node *cur = root;
		FOR(i,0,sz(s)-1) {
			FOR(c,0,26) if (last_occ[c] >= i) {
				if (cur->go[c] && cur->go[c]->is_end) res++;
			}
			cur = cur->go[s[i]-'a'];
		}
	}
	cout << res << endl;
}



Measured memory_bytes: 223188
package main

import(
	"fmt"
	"sort"
)

type Task struct{
	a,b int
}

type Tasks []Task

func (t Tasks) Len() int{return len(t)}
func (t Tasks) Less(i, j int) bool{return t[i].b<t[j].b}
func (t Tasks) Swap(i, j int){t[i],t[j]=t[j],t[i]}

func main(){
	var(
		n int
	)
	fmt.Scanln(&n)
	t:=make([]Task,n)
	for i:=0;i<n;i++{
		fmt.Scanln(&t[i].a,&t[i].b)
	}
	sort.Sort(Tasks(t))
	time:=0
	for i:=0;i<n;i++{
		time+=t[i].a
		if time>t[i].b{
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}

Measured memory_bytes: 9672
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define fo(i,n) for(int i=0;i<(n);i++)
#define inp(a) int a;cin>>a;
#define inpa(a,n)vector<int> a(n);fo(i,n)cin>>a[i];
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
using namespace std;
#define int ll
// #define MAX 20
#define INF (int)1e18

template<class T> ostream& operator<<(ostream& cout,vector<T> V)
{cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}
template<class L,class R> ostream& operator<<(ostream& cout,pair<L, R> P)
{return cout<<'('<<P.F<<','<< P.S<<')';}


signed main()
{
	fio
	inp(n) inp(m)
	if(n>m)
		swap(n,m);
	if(n==1)
	{
		cout<<1<<'\n';
		return 0;
	}
	int ans=n*m;
	if(ans%2)
		ans=(ans/2)+1;
	else
		ans/=2;
	cout<<ans<<'\n';
	printclock;
}


Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    n,a,b = parseMap(split(readline()))
    ab = a+b
    s = readline()
    fc = 1
    count = 0
    for rep in s
        if rep=='c'
            println("No")
        elseif rep=='a'
            if count<ab
                count += 1
                println("Yes")
            else
                println("No")
            end
        else 
            if count<ab && fc<=b
                count += 1
                fc += 1
                println("Yes")
            else
                println("No")
            end
        end
    end
end

main()

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

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define REP(i,n) for(int i=0; i < (n); ++i)
#define SIZE(c) (int) (c).size()
#define ALL(c) (c).begin(), (c).end()
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
#define FWD(i,a,b) for (int i=(a); i<(b); ++i)
#define BCK(i,a,b) for (int i=(a); i>(b); --i)
#define PI 3.14159265358979311600
#define pb push_back
#define mp make_pair
#define st first
#define nd second

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

typedef vector < int > VI;
typedef vector<ll> VL;

typedef long double K;

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

	int n;
	cin >> n;
	vector<int> a(n);
	int total = 1;
	int odd = 1;
	for (auto& item : a) {
		cin >> item;
		total *= 3;
		if (item % 2 == 0) odd *= 2;
	}
	cout << total-odd << '\n';

	return 0;
}

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }

ll mod_num = 1e9+7;

int main() {
    ll h,w; cin >> h >> w;
    vector<vector<char>> a(h,vector<char>(w));
    rep(i, h) rep(j, w) cin >> a[i][j];


    // dpテーブル
    // dp[0][0]からdp[i][j]へたどり着くルートが何通りかを記録する
    vector<vector<ll>> dp(h,vector<ll>(w,0));
    // 初期位置は1にしておく
    dp[0][0] = 1;
    rep(i, h) rep(j, w)  {
        if(a[i][j] == '.') {
            if(i > 0) dp[i][j] += dp[i-1][j]%mod_num;
            if(j > 0) dp[i][j] += dp[i][j-1]%mod_num;
            dp[i][j]%mod_num;
        } else {
            dp[i][j] = 0;
        }

    }

    cout << dp[h-1][w-1]%mod_num << endl;
    return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define debug cerr << "-- " << __LINE__ << " --" << endl
#define MOD 1000000007
typedef long long int ll;

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
template <typename T> string to_string(const vector<T> &xs) {string s="["; for(int i=0;i<xs.size();i++) s += (i>0 ? " " : "") + to_string(xs[i]); return s + "]";}


// #include<bits/stdc++.h>
// using namespace std;		
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template<class T> using TreeSet = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// set と同様に .insert など使え，さらに log オーダで
// .find_by_order(idx) で idx 番目への iterator が返る（存在しない場合は .end() がたぶん返る）
// .order_of_key(key) で「key 以上の最初の要素が何番目か」が返る


ll extgcd(ll a, ll b, ll &x, ll &y) {
  ll g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
ll gcd(ll a, ll b) { ll x, y; return extgcd(a, b, x, y);}

class llm{
	ll n;
public:
	llm(){n = 0;}
	llm(ll n){this->n = (n >= 0) ? (n % MOD) : (MOD - 1 - (-n-1 % MOD));}
	operator ll() const {return n;}
	llm operator+(const llm &y) const{ return llm((ll)*this + (ll)y);}
	llm operator+=(const llm &y) { *this = *this + y; return *this;}
	llm operator-(const llm &y) const{ return llm((ll)*this - (ll)y);}
	llm operator-=(const llm &y) { *this = *this - y; return *this;}
	llm operator-() const{ return llm(0) - *this;}
	llm operator*(const llm &y) const{ return llm((ll)*this * (ll)y);}
	llm operator*=(const llm &y) { *this = *this * y; return *this;}
	llm operator/(const llm &y) const{ return *this * y.inv();}
	llm operator/=(const llm &y) { *this = *this / y; return *this;}
	llm inv() const{
		ll x, y;
		if (extgcd(n, MOD, x, y) == 1) return llm(x);
  		return llm(0); // unsolvable
	}
	friend istream& operator >> (istream& os, llm& x);
	friend ostream& operator << (ostream& os, const llm& x);
};
istream& operator >> (istream& is, llm& x){ll n; is >> n; x = llm(n); return is;}
ostream& operator << (ostream& os, const llm& x){os << (ll)x; return os;}

template<typename T> T comb(ll n, ll k){
	T ret = 1;
	for(ll i=1;i<=k;i++) ret = ret * T(n - k + i) / T(i);
	return ret;
}


ll Q;

int main(void){
	cin >> Q;
	ll bias = 0, minval = 0, median = 0, preMedian = 0;
	TreeSet<pair<ll, ll>> ts;
	for(int i=0;i<Q;i++){
		ll cmd; cin >> cmd;
		if (cmd == 1){
			ll a, b; cin >> a >> b;
			bias += b;
			ts.insert(mp(a, i));
			preMedian = median;
			median = (*(ts.find_by_order((ts.size()-1)/2))).first;
			if (ts.size() >= 2){
				// minval の更新．
				if (ts.size() % 2 == 0){
					minval += llabs(preMedian - median); 
				}else{
					if (median < preMedian){
						minval += 2 * llabs(preMedian - median); 
					}
				}
				minval += llabs(a - median);
			}
		}else{
			cout << median << " " << minval + bias << endl;
		}
	}
	
	


    return 0;
}




Measured memory_bytes: 12800
#![allow(unused_imports)]
use proconio::{input, fastout};
use proconio::marker::*;

#[fastout]
fn main() {
    input! {
    a: usize,
    b: usize,
    c: usize,
    d: usize
    }
    let ans = if a + b == c + d {
        "Balanced"
    } else if a + b > c + d {
        "Left"
    } else {
        "Right"
    };
    println!("{}", ans);
}


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


int main() {
  int a , b, c, d;
  cin >> a >> b >> c >> d;
  int s = min(a,b);
  int t = min(c,d);
  cout << s+t << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
                                                                   
int main(){
  int r,c;
  //行数r,列数c
  cin >> r >> c;
 int  arr[r+1][c+1];
  REP(i,r){
    REP(j,c){
      if(i==0)
        arr[r][j]=0;
      cin >> arr[i][j];
      arr[r][j] +=arr[i][j];
    }
  }
  int sum =0;
 // int total1[c];
  vector <int> total;
  REP(i,r+1){
    REP(j,c+1){
      if(j==c)
        cout << sum;
      else if(j!=c){
        cout << arr[i][j]<<' ';
        sum+=arr[i][j];
      }
    }
    sum=0;
    cout << endl;
  }
}

Measured memory_bytes: 1196
package main

import (
	"fmt"
)

func main() {
	var a, b, c, k int
	fmt.Scan(&a, &b, &c, &k)

	count := 0

	if k > a {
		count += a
		k -= a
		if k > b {
			k -= b
			if k > c {
				count -= c
			} else {
				count -= k
			}
		}
	} else {
		count = k
	}

	fmt.Println(count)
}


Measured memory_bytes: 1752
N = int(input())
L = list(map(int, input().split()))

if N <= 2:
    print(0)
    exit()
    
count = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            rod = [L[i], L[j], L[k]]
            condition = set(rod)
            rod = sorted(rod)
            if rod[0] + rod[1] > rod[2] and len(condition) == 3:
                count += 1
                
print(count)

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acosl(-1);

#define rep(i,n) for(int i=0; i<(n); ++i)
#define all(n) n.begin(),n.end()

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

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	int k;
	cin >> k;

	queue<ll> q;
	for(int i = 1; i < 10; i++){
		q.push(i);
	}
	rep(i, k-1){
		int x = q.front();
		q.pop();
		if(x % 10 != 0){
			q.emplace(10LL * x + (x % 10) - 1);
		}
		q.emplace(10LL * x + x % 10);
		if(x % 10 != 9){
			q.emplace(10LL * x + (x % 10) + 1);
		}
	}

	cout << q.front() << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
//
struct SegTree{
	//
	int n;
	vector<int> dat;
	//
	SegTree(int n_){
		n=1;
		while(n<n_){
			n*=2;
		}
		dat=vector<int>(n*2-1,INT_MAX);
	}
	//
	void update(int k,int a){
		k+=n-1;
		dat[k]=a;
		while(k){
			k=(k-1)/2;
			dat[k]=min(dat[k*2+1],dat[k*2+2]);
		}
	}
	//
	int query(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1){
			r=n;
		}
		if(r<=a||b<=l){
			return INT_MAX;
		}else if(a<=l&&r<=b){
			return dat[k];
		}else{
			int va=query(a,b,k*2+1,l,(l+r)/2);
			int vb=query(a,b,k*2+2,(l+r)/2,r);
			return min(va,vb);
		}
	}
};
//
int main(){
	int N,Q;
	cin>>N>>Q;
	SegTree Seg(N);
	while(Q--){
		int C,X,Y;
		cin>>C>>X>>Y;
		if(C==1){
			cout<<Seg.query(X,Y+1)<<endl;
		}else{
			Seg.update(X,Y);
		}
	}
	return 0;
}


Measured memory_bytes: 5000
import bisect
def main():
    s = input()
    t = input()
    if not set(t).issubset(set(s)):
        return -1
    d = {}
    n = len(s)
    for i, v in enumerate(s):
        if v in d:
            d[v].append(i)
            d[v].append(i + n)
        else:
            d[v] = [i, i+n]
    for i in d:
        d[i] = sorted(d[i])
    m = 0
    j = 0
    for i in t:
        ind = bisect.bisect_left(d[i], j)
        m += d[i][ind] - j + 1
        if d[i][ind] >= n:
            j = d[i][ind] - n + 1
        else:
            j = d[i][ind] + 1
    return m
print(main())


Measured memory_bytes: 13228
N = gets.to_i
name_march = Hash.new(0)

N.times{|i|
    s = gets.chomp
    
    case s[0]
    when "M", "A", "R", "C", "H" then
        name_march[s[0]] += 1
    end
}

a = name_march.values

puts (0...a.size).inject(0){|sum, i|
    (i+1...a.size).each{|j|
        (j+1...a.size).each{|k|
            sum += a[i] * a[j] * a[k]
        }
    }
    sum
}

Measured memory_bytes: 2044
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
    int n,x[100]={},y[100]={};
    cin>>n;
    for(int i=0;i<n;i++)cin>>x[i];
    for(int i=0;i<n;i++)cin>>y[i];
    double d[4];
    for(int i=0;i<4;i++)d[i] = 0.0;
    
    for(int p= 1;p<=3;p++){
        for(int i=0;i<n;i++){
            d[p] += pow(fabs(x[i]-y[i]),p);
        }
        d[p] = pow(d[p],1.0/p);
    }
    for(int i=0;i<n;i++){
        d[0] = max(d[0],fabs(x[i]-y[i]));
    }
    printf("%lf\n",d[1]);
    printf("%lf\n",d[2]);
    printf("%lf\n",d[3]);
    printf("%lf\n",d[0]);
    
    return 0;
}




Measured memory_bytes: 3340
#!/usr/bin/env python3
import sys


def solve(N: int):
    print(N // 3)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/compress.hpp"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#ifndef COMPRO_COMPRESS
#define COMPRO_COMPRESS

template <class T> class Compress {
public:
  explicit Compress(const std::vector<T> &argv) {
    isBuilt = false;
    add(argv);
  }

  Compress() { isBuilt = false; }

  void add(const std::vector<T> &argv) {
    for (const auto &x : argv) {
      add(x);
    }
  }
  void add(const T x) {
    assert(!isBuilt);
    v.emplace_back(x);
  }

  void build() {
    isBuilt = true;
    std::sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
  }

  int get(const T x) const {
    assert(isBuilt);
    return lower_bound(v.begin(), v.end(), x) - v.begin();
  }

  const T &operator[](const int k) const { return v[k]; }

  int size() const { return v.size(); }

private:
  std::vector<T> v;
  bool isBuilt;
};
#endif
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << endl; }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}


#line 3 "tmp.cpp"

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

  int n;
  cin >> n;
  vl vx1, vx2, vy1, vy2;
  Compress<ll> vx, vy;
  REP(i, n) {
    int x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    vx1.emplace_back(x1);
    vx2.emplace_back(x2);
    vy1.emplace_back(y1);
    vy2.emplace_back(y2);
  }

  vx.add(vx1);
  vx.add(vx2);
  vy.add(vy1);
  vy.add(vy2);
  vx.build();
  vy.build();

  REP(i, n) {
    vx1[i] = vx.get(vx1[i]);
    vx2[i] = vx.get(vx2[i]);
    vy1[i] = vy.get(vy1[i]);
    vy2[i] = vy.get(vy2[i]);
  }

  vector<vi> imos(2 * n, vi(2 * n, 0));
  REP(i, n) {
    imos[vx1[i]][vy1[i]]++;
    imos[vx2[i]][vy1[i]]--;
    imos[vx1[i]][vy2[i]]--;
    imos[vx2[i]][vy2[i]]++;
  }

  REP(i, 2 * n) {
    FOR(j, 1, 2 * n) { imos[i][j] += imos[i][j - 1]; }
  }
  REP(j, 2 * n) {
    FOR(i, 1, 2 * n) { imos[i][j] += imos[i - 1][j]; }
  }
  int xSize = vx.size();
  int ySize = vy.size();

  ll ans = 0;
  REP(i, xSize - 1) {
    REP(j, ySize - 1) {
      if (imos[i][j] > 0)
        ans += (vx[i + 1] - vx[i]) * (vy[j + 1] - vy[j]);
    }
  }

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



Measured memory_bytes: 65612
import java.util.*;

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

        String s = sc.next();

        if(s.charAt(0) != s.charAt(1) && s.charAt(1) != s.charAt(2) && s.charAt(2) != s.charAt(0)){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 22740
import sys
import numpy as np

N, M = [int(_) for _ in input().split()]

if M == 0:
    if N == 1:
        print("0")
    else:
        ans = [0] * N
        ans[0] = 1
        print("".join(map(str, ans)))
    sys.exit()

S, C = np.array([[int(_) for _ in input().split()] for i in range(M)]).T

ans = [-1] * N

for i in range(M):
    j = int(S[i]) - 1
    if ans[j] == -1 or ans[j] == C[i]:
        ans[j] = C[i]
    else:
        print("-1")
        sys.exit()

if N >= 2 and ans[0] == 0:
    print("-1")
    sys.exit()

if N >= 2 and ans[0] == -1:
    ans[0] = 1

for i in range(1, N):
    if ans[i] == -1:
        ans[i] = 0

s = "".join(map(str, ans))
print(s)


Measured memory_bytes: 26936
import std.algorithm;
import std.range;
import std.stdio;
import std.math;
import std.array;
import std.string;
import std.conv;

/// 数列の読み込み
auto readNums(T = int)() {
	return readln().chomp.split.map!(to!T).array;
}

/// 数の読み込み
auto readNum(T = int)() {
	return readNums!T.front;
}

/// 指定行数読み込み
auto readRows(size_t rows) {
	return generate(() => readln().chomp).take(rows).array;
}

/// 範囲の計算
auto range(T)(T a, T b, T c, T d) {
    auto start = max(a, c);
    auto end = max(b, d);
    return (start < end) ? tuple(start, end) : tuple(cast(T) 0, cast(T) 0);
}

auto maxElement(R)(R r) {
    return r.reduce!((a, b) => max(a, b));
}

auto minElement(R)(R r) {
    return r.reduce!((a, b) => min(a, b));
}

void main() {
	const nums = readNums();
	immutable diff = abs(nums[0] - nums[1]);
	if(diff <= 16 - (nums[0] + nums[1])) {
		writefln("Yay!");
	} else {
		writefln(":(");
	}
}

Measured memory_bytes: 256
def solution(s, t):
    cs = [0 for i in xrange(26)]
    for c in s:
        cs[ord(c) - ord('a')] += 1
    ps = { }
    for k in cs:
        if k > 0:
            if k not in ps:
                ps[k] = 1
            else:
                ps[k] += 1
    ct = [0 for i in xrange(26)]
    for c in t:
        ct[ord(c) - ord('a')] += 1
    for k in ct:
        if k > 0:
            if k not in ps:
                return False
            if ps[k] == 0:
                return False
            ps[k] -= 1
    return True

def main():
    s = raw_input().strip()
    t = raw_input().strip()
    if solution(s, t):
        print 'Yes'
    else:
        print 'No'

if __name__ == '__main__':
    main()


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

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

using namespace std;

typedef long long ll;

const int N_MAX = 102;

int n;

int a[N_MAX], b[N_MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    bool ok = false;
    for(int i = 3; i <= n; i++)
        if(a[i] == b[i] && a[i - 1] == b[i - 1] && a[i - 2] == b[i - 2])
            ok = true;
    if(ok == true)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}



Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define maxn 120000
using namespace std;
typedef long long LL;
LL a[3][maxn];
LL f[3][maxn]; 
int main(){
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	for(int i = 1; i <= N; i += 1)
		for(int j = 0; j < 3; j += 1) cin >> a[j][i];
	for(int i = 1; i <= N; i += 1)
		for(int j = 0; j < 3; j += 1)
			for(int k = 0; k < 3; k += 1) if(j != k)
				f[j][i] = max(f[j][i], f[k][i - 1] + a[j][i]);
	cout << max(max(f[0][N], f[1][N]), f[2][N]);
} 


Measured memory_bytes: 5248