akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cmath>
#include<vector>
#include<bitset>
#include<bitset>
#include<string>
#include<utility>
#include<queue>

using namespace std;
long long int bign = 1000000007;

int main(){
    int n,m;
    cin >> n >> m;
    vector<bool> bre(n+1,false);
    int a;
    for(int i=0;i<m;i++){
        cin >> a;
        bre.at(a)=true;
    }
    vector<pair<long long int,long long int>> res(n+1,make_pair(0,0));
    // (1段前から, 2段前から直接)
    res.at(0).first=1;
    // res.at(0).second=1;
    if(!bre.at(1))res.at(1).first=1;
    for(int i=2;i<=n;i++){
        
        if(bre.at(i))continue;
        if(bre.at(i-1) && bre.at(i-2)){
            cout << 0 <<endl;
            return 0;
        }
        else if(bre.at(i-1))res.at(i).second=(res.at(i-2).first+res.at(i-2).second)%bign; 
        else if(bre.at(i-2))res.at(i).first=res.at(i-1).second;
        else {res.at(i).first = (res.at(i-1).first+res.at(i-1).second)%bign;
        res.at(i).second= (res.at(i-2).first + res.at(i-2).second)%bign;}
        
    }
    // for(int i=0;i<=n;i++){
    //     cout << res.at(i).first << ","<< res.at(i).second << endl;
    // }
    cout << (res.at(n).first+res.at(n).second)%bign << endl;
    return 0;
}

Measured memory_bytes: 4468
n = int(input())
t = []
sum = 0

line = input().split(" ")
for i in range(n):
    t.append(int(line[i]))
    sum += int(line[i])

m = int(input())
for i in range(m):
    line = input().split(" ")
    p = int(line[0]) - 1
    x = int(line[1])
    for j in range(len(t)):
        if j == p:
            comp = sum - t[j] + x
    print(comp)

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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long ll;

int main() {
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;
    int RL = 0;
    char t = 0;
    rep(i, n){
        if(t == 0) t = s[i];
        else{
            if(t == 'R' && s[i] == 'L'){
                RL++;
            }
        }
        t = s[i];
    }
    int un = RL*2 + (s[0] == 'L') + (s[n-1] == 'R');
    un = max((un - 2*k),0);
    cout << min((n - un), (n-1)) << endl;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(){
  int a,b,c,d;
  cin >> a>>b>>c>>d;
  if((a+b)>(c+d)){
  cout << "Left";
}
else if((a+b)<(c+d)){
  cout <<"Right";
}else
cout <<"Balanced";
  return 0;
}


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

N,M,K = list(map(int, input().rstrip().split()))
#-----
# Calculate the Factorial and it's Inverse Element
fact = [0]*(N+1)
fact_inv = [0]*(N+1)
inv = [0]*(N+1)

mod = 998244353

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2, N+1):
    fact[i] = (fact[i-1] * i) % mod
    inv[i] = mod - ( inv[mod%i] * (mod // i) ) % mod
    fact_inv[i] = ( fact_inv[i-1] * inv[i] ) % mod

#-----
# Calculate (M-1) raised to the power of "0 to N-1"
pow_M1 = [0]*N
pow_M1[0] = 1

for i in range(1, N):
    pow_M1[i] = ( pow_M1[i-1] * (M-1) ) % mod

#-----
ans = 0

for i in range(K+1):
    comb = ( fact[N-1] * fact_inv[i] * fact_inv[N-1-i] ) % mod
    
    ans += ( comb * M * pow_M1[N-i-1] ) % mod
    ans %= mod

print(ans)


Measured memory_bytes: 40300
#include <bits/stdc++.h>
 
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;

typedef tree<
ll,
null_type,
less<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
// ordered_set X;
// *X.find_by_order(i) = ith largest element (counting from zero)
// X.order_of_key(k) = number of items in X < k (strict lt)

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

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

    int N;
    ll x;
    
    cin >> N >> x;

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

    sort(all(A));

    int ans = 0;
    for (int i=0;i<N;i++) {
        if (x >= A[i]) {
            x-= A[i];
            ans++;
        }
    }
    if (x > 0 && ans == N) ans = N-1;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int A,B,C;

int main(){
	cin>>A>>B>>C;
	if(A+B<C) cout<<"NA"<<endl;
	else cout<<max(0,C-A)<<endl;
}


Measured memory_bytes: 3092
N=int(input())
L=input()
L=L.replace('o','1')
L=L.replace('x','0')
L=list(map(int,list(L)))
init = [[1, 1], [1, 0], [0, 1], [0, 0]]
ans = -1
for ii in init:
  ret = [None]*(N)
  ret[0] = ii[1] 
  pR = ii[0]
  for i in range(1, N):
    ret[i]= ~ ((~ (ret[i-1] ^ L[i-1])) ^ pR)
    pR = ret[i-1]
  if ii[0]==ret[-1] and ret[0]==~ ((~ (ret[-1] ^ L[-1])) ^ pR):
    ans = ret
    break

if ans == -1:
  print(ans)
else:
  ans=list(map(str,ans))
  ans=''.join(ans)
  ans=ans.replace('1','S')
  ans=ans.replace('0','W')
  print(ans)

Measured memory_bytes: 11620
#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define LL                      long long
#define Ulong                   unsigned long long
#define REP(i,n)                for(long long i=0; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-14
#define F                       first
#define S                       second
#define di(x)                   int x; input(x)
#define in(x)                   input(x)
#define in2(x,y)                in(x),in(y)
#define in3(x,y,z)              in(x),in2(y,z)
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl
#define nl                      cout<<endl
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("/home/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE                   freopen("out.txt","w",stdout)
template<class T> inline void input(T &x) {
    char c = getchar();x = 0;
    int neg = 0;
    for(; ((c<48 || c>57) && c != '-'); c = getchar());
    if(c=='-'){neg = 1;c = getchar();}
    for(; c>47 && c<58 ; c = getchar()){x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x = -x;
}
inline long long bigmod(long long p,long long e,long long M){
    long long ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/


const int N = 1001;

int main()
{
    int a,b;
    cin >> a >> b;
    if(a + b == 15) cout << '+';
    else if(a * b == 15) cout << '*';
    else cout << 'x';
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

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

    sort(a.begin(), a.end());
    int ans = a.back() - a.front();
    cout << ans << endl;

    return 0;
}


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

int main(){
  string S;
  cin >> S;
  int price = 700;

  if (S[0] == 'o')
  price += 100;
  if (S[1] == 'o')
  price += 100;
  if (S[2] == 'o')
  price += 100;

  cout << price << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
 
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 (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

int main(){
    int n;
    string s,t;
    cin>>n>>s>>t;
    int m=0;
    rep(i,n){
        int flag=1;
        rep(j,i+1){
            if(s[n-1-j]!=t[i-j]){
                flag=0;
                break;
            }
        }
        if(flag)m=i+1;
    }
    cout<<2*n-m<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;            //

int main(void)
{
    char a, b;
    cin >> a >> b;

    char ans;
    if (a == b)
    {
        ans = 'H';
    }
    else
    {
        ans = 'D';
    }
    cout << ans << endl;
    return (0);
}

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

char a[205], b[205];

int main(){
	int k, ans;
	char *p, *q, *wp, *wq;
	char *s[3] = { "IDENTICAL", "CLOSE", "DIFFERENT" };

	while (scanf("%s", a) && a[0] != '.') {
		scanf("%s", b); p = a, q = b; ans = -1, k = 0;
		while (*p && *q) {
			if (*p != *q) {
			    ans = 2; break;
			    }
			if (*p == '"') {
			    wp = ++p, wq = ++q;
				while (*p != '"'){
				    p++;
				}while (*q != '"'){
				    q++;
				}
				*p = *q = 0;
				k += 1 - (strcmp(wp, wq) == 0);
				if (k > 1) {
				    ans = 2;
				    break;
				    }
			}
			p++, q++;
		}
		if (ans < 0){
		    if (*p == *q){
		        ans = k;
		        }else{
		            ans = 2;
		        }
		}
		puts(s[ans]);
	}
	return 0;
}


Measured memory_bytes: 2032
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
	string s;
	cin>>s;
	int A,B,C,D;
	A=s[0]-'0';
	B=s[1]-'0';
	C=s[2]-'0';
	D=s[3]-'0';
	if (A+B+C+D==7){
		cout<<A<<"+"<<B<<"+"<<C<<"+"<<D<<"=7"<<endl;
		return 0;
	}
	if (A+B+C-D==7){
		cout<<A<<"+"<<B<<"+"<<C<<"-"<<D<<"=7"<<endl;
		return 0;
	}
	if (A+B-C+D==7){
		cout<<A<<"+"<<B<<"-"<<C<<"+"<<D<<"=7"<<endl;
		return 0;
	}
	if (A+B-C-D==7){
		cout<<A<<"+"<<B<<"-"<<C<<"-"<<D<<"=7"<<endl;
		return 0;
	}
	if (A-B+C+D==7){
		cout<<A<<"-"<<B<<"+"<<C<<"+"<<D<<"=7"<<endl;
		return 0;
	}
	if (A-B+C-D==7){
		cout<<A<<"-"<<B<<"+"<<C<<"-"<<D<<"=7"<<endl;
		return 0;
	}
	if (A-B-C+D==7){
		cout<<A<<"-"<<B<<"-"<<C<<"+"<<D<<"=7"<<endl;
		return 0;
	}
	if (A-B-C-D==7){
		cout<<"A"<<"-"<<B<<"-"<<C<<"-"<<D<<"=7"<<endl;
		return 0;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <tuple>
#include <string>
#include <set>
#include <map>
using namespace std;
using ll = long long;



int main() {
	int n, d,sum=0,ans=0;
	cin >> n >> d;
	while (sum < n) {
		sum += 2*d+1;
		ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#include<cstdlib>
#define _t putchar(32)
#define _e putchar(10)
#define inf 2147483647
#define ine -2147483647
#define lb(x) ((x)&(-(x)))
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
bool o;
char ch,SSS[1<<17],*A=SSS,*B=SSS;
inline char gc(){
	return A==B&&(B=(A=SSS)+fread(SSS,1,1<<17,stdin),A==B)?EOF:*A++;
}
template <typename _Tp> inline void rd(_Tp &x);
template <typename _Tp> inline void wr(_Tp x);
template <typename _Tp> inline _Tp mx(_Tp x,_Tp y);
template <typename _Tp> inline _Tp mn(_Tp x,_Tp y);
int n,a[200001],b[200001],s1[200001],s2[200001];
int sum,m,st[200001],cnt,s[200001],p[200001];
int ans[200001],l,r,p1,p2;
int qwq[200001],gu;
inline void sp(int &x,int &y){
	x^=y^=x^=y;
}
int main(){
	rd(n);
	for(int i=1;i<=n;i++) rd(a[i]),s1[a[i]]++;
	for(int i=1;i<=n;i++){
		rd(b[i]),s2[b[i]]++;
		if(a[i]==b[i]) st[++cnt]=i,sum++,s[a[i]]++;
		if(s[m]<s[a[i]]) m=a[i];
	}
	if(s[m]<=sum-s[m]){
		puts("Yes");
		memcpy(ans,b,sizeof(b));
		for(int i=1;i<=cnt;i++) p[i]=st[i+s[m]>cnt?i+s[m]-cnt:i+s[m]];
		for(int i=1;i<=cnt;i++) ans[st[i]]=b[p[i]];
		for(int i=1;i<n;i++) wr(ans[i]),_t;
		wr(ans[n]);
		return 0;
	}
	if(s1[m]+s2[m]>n){
		printf("No");
		return 0;
	}
	puts("Yes");
	for(int i=1;i<=n;i++)
	if(a[i]!=b[i]&&a[i]!=m&&b[i]!=m) qwq[++gu]=i;
	for(l=1;a[st[l]]!=m;l++);
	for(r=l+1;r<=cnt&&a[st[r]]==m;r++);
	r--;
	p1=l;
	for(int i=1;i<l;i++) sp(b[st[i]],b[st[p1++]]);
	for(int i=r+1;i<=cnt;i++) sp(b[st[i]],b[st[p1++]]);
	p2=1;
	while(p1<=r) sp(b[st[p1++]],b[qwq[p2++]]);
	for(int i=1;i<n;i++) wr(b[i]),_t;
	wr(b[n]);
}
template <typename _Tp>
    inline void rd(_Tp &x){
    	o=0;
        x=0;
    	while (ch^45&&(ch<48||ch>57)) ch=gc();
    	if(ch==45)o=1,ch=gc();
        while(ch>47&&ch<58){
			x=(x<<1)+(x<<3)+(ch^48);
			ch=gc();
		}
    	if(o) x=-x;
	}
template <typename _Tp>
    inline void wr(_Tp x){
        if(x<0) x=-x,putchar(45);
        if(x<10){
            putchar(x+48);
            return;
        }
        wr(x/10);
        putchar(x%10+48);
    }
template <typename _Tp>
	inline _Tp mx(_Tp x,_Tp y){
		return x>y?x:y;
	}
template <typename _Tp>
	inline _Tp mn(_Tp x,_Tp y){
		return x<y?x:y;
	}


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

using namespace std;

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

    vector<int> p;
    int a;

    for(int i=0;i<n;i++){
        cin >> a;
        p.push_back(a);
    }

    for(int i=0;i<n+6;i++){
        if(std::find(p.begin(), p.end(), x-i)==p.end()){
            cout << x-i;
            return 0;
        }  
        if(std::find(p.begin(), p.end(), x+i)==p.end()){
            cout << x+i;
            return 0;
        }
    }

}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pr;
typedef vector<pr> vp;
typedef vector<vp> vpp;
typedef vector<vector<ll> > graph;
#define pb push_back
#define mp make_pair
#define maxi INT_MAX
#define mini INT_MIN
#define endl '\n'
void set_val(vector<ll>& v, ll val){for(ll i=0;i<v.size();i++) v[i]=val;}

ll mod = pow(10,9) + 7;
ll modulo = 998244353;
double pi = 3.141592653589793238;
ll i_mov[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
ll j_mov[8] = {1, 1, 1, 0, -1, -1, -1, 0};

vector<vector<int>> g;
vector<int> parent, depth, subsize;

ll power(ll a, ll n)
{
    if(n==0)
    return 1;
    ll temp = power(a,n/2);
    if(n%2==0)
    return (temp*temp)%mod;
    return (((temp*temp)%mod)*a)%mod;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout<<fixed;
    cout<<setprecision(10);
    ll n, k;
    cin>>n>>k;
    ll ans = 0;
    for(ll i = k;i<=n+1;i++)
    {
        ans = (ans+ (i*(n+1) - (i*i) + 1)%mod)%mod;
    }
    cout<<ans<<endl;
    
    
    
} 

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli mod=1000000007;

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cout.tie(NULL);
	lli x;
	cin>>x;
	cout<<1000*(x/500)+5*((x%500)/5)<<endl;
}


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

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {
          
     
			var inputArray = retreiveLongArray();
			var inputCount = 2;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			long N = inputArray[0];
			long K = inputArray[1];


			var inpArray = retreiveLongArray();

			var currentRight = new Dictionary<long, long>();

			for (int i = 0; i < N; i++) {
				currentRight.Add(i, inpArray[i]);
			}

			//k回処理する
			for (int i = 0; i < K; i++) {
				var nextRight = new Dictionary<long, long>();

				for (int j = 0; j < N; j++) {
					nextRight.Add(j, 0);
				}

				for (int j = 0; j < N; j++) {
					var right = currentRight[j];

					var start = Math.Max(j - right, 0);
					var end = Math.Min(j + right, N - 1);
					//累積和を使う
					nextRight[start]++;
					if (end<N-1) {
						nextRight[end + 1]--;
					}

				}

				//累積和
				for (int j = 1; j < N; j++) {
					nextRight[j] += nextRight[j - 1];
				}

				var shusoku = true;
				for (int j = 0; j < N; j++) {
					if (nextRight[j] != currentRight[j]) {
						shusoku = false;
					}
				}
				if (shusoku) {
					break;
				}


				currentRight = nextRight;

				//検証用
				//答えの出力
				//var ansArray2 = currentRight.Select(x => x.Value).ToArray();

				//var ans2 = string.Join(" ", ansArray2);
				//Console.WriteLine(ans2);
			}


			//答えの出力
			var ansArray = currentRight.Select(x => x.Value).ToArray();

			var ans = string.Join(" ", ansArray);
			Console.WriteLine(ans);

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}


Measured memory_bytes: 148452
#include<iostream>
#include<string>
#include<math.h>

using namespace std;

int main(void)
{
	int ans=0;
	while(1)
	{
		string s;
		cin>>s;
		if(cin.eof())break;
		int k=0;
		for(int i=s.length()-1;i>=0;i--)
		{
			if('0'<=s[i]&&s[i]<='9')
			{
				ans+=pow(10.0,k)*(s[i]-'0');
				k++;
			}
			else k=0;
		}
	}
	cout<<ans<<endl;
}

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

class Main {
    public static void main(String [] args){
        Scanner scan = new Scanner(System.in);
        
        while(true){
            int s = 0;
            int n = scan.nextInt();
            int x = scan.nextInt();
            
            if(n == 0){
                break;
            }
            
            for(int i = 1; i <= n; ++i){
                for(int j = i + 1; j <= n; ++j){
                    for(int k = j + 1; k <= n; ++k){
                        if(i + j + k == x){
                            ++s;
                        }
                    }
                }
            }
            
            System.out.println(s);
        }
    }
}

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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

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

  ll a = 2, b = 1, c = 1;
  rep(i, 2, n + 1) {
    ll c = a + b;
    a = b;
    b = c;
    if(i == n) cout << b << endl;
  }
}


Measured memory_bytes: 256
#include <vector>
#include <iostream>

using namespace std;
#define maxn 200001
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

long long n, ans;
vector<long long> h(maxn, 0);
vector<long long> a(maxn, 0);
vector<long long> dp(maxn, 0);
vector<long long> BIT(maxn, 0);

void update(long long ind, long long val) {
	while (ind < maxn) {
		BIT[ind] = max(BIT[ind], val);
		ind += (ind & -ind);
	}
}

long long query(long long ind) {
	long long res = 0;
	while (ind > 0) {
		res = max(res, BIT[ind]);
		ind -= (ind & -ind);
	}
	return res;
}

int main() {

	cin >> n;
	for (long long i = 1; i <= n; i++) cin >> h[i];
	for (long long i = 1; i <= n; i++) cin >> a[i];

	for (long long i = 1; i <= n; i++) {
		long long val = query(h[i]);
		dp[i] = a[i] + val;
		update(h[i], dp[i]);
		ans = max(ans, dp[i]);
	}

	cout << ans;

	return 0;
}

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

int main() {
    int k, s, d, a=0;
    cin >> k >> s;
    
    for(int i=0; i<k+1; i++){
    		for(int j=0; j<k+1; j++){
                            d = s - i - j;
    			    if(d >= 0 && d <= k) a++;
    		}
    }
    cout << a << "\n";
}


Measured memory_bytes: 256
n,m = map(int,input().split())
P = [list(map(int,input().split()))+[0,i] for i in range(m)]
P.sort(key = lambda x:x[1])
city = {}
for p in P:
    if p[0] in city:
        city[p[0]] += 1
    else:
        city[p[0]] = 1
    p[2] = city[p[0]]
P.sort(key = lambda x:x[3])
for p in P:
    print(str(p[0]).zfill(6)+str(p[2]).zfill(6))


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

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

fn main() {
    input! {
        n: usize,
        k: usize,
        v: [i64; n],
    }

    let mut v: Vec<i64> = v.clone();
    v.sort_by(|a, b| b.cmp(a));
    
    let s1: i64 = v.iter().sum();
    let s2: i64 = v.iter().take(k).sum();
    let s: i64 = s1 - s2;

    if s > 0 {
        println!("{}", s)
    } else {
        println!("0")
    }
}


Measured memory_bytes: 8444
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
const ll MOD = 998244353;
const ll INF = 1e18;
using namespace std;

ll arr[20][20];

main(){    
    #ifdef XOX
        freopen("D:\\V S Code\\cpp\\competitiveProgramming\\Input.txt", "r", stdin);
        freopen("D:\\V S Code\\cpp\\competitiveProgramming\\OPT.txt", "w", stdout);
    #endif

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m;
    ll x;
    cin >> n >> m >> x;
    ll c[20];
    for(int i = 0; i < n; i++){
        cin >> c[i];
        for(int j = 0; j < m; j++){
            cin >> arr[i][j];
        }
    }

    ll ans = INF, cost;
    int tmp[m];
    for(int i = 0; i < (1 << n); i++){
        memset(tmp, 0, sizeof(tmp));
        cost = 0;
        for(int j = 0; j < n; j++){
            if(i&(1 << j)){
                cost += c[j];
                for(int l = 0; l < m; l++)  tmp[l] += arr[j][l];
            }
        }

        bool state = true;
        for(int j = 0; j < m; j++)  if(tmp[j] < x)  state = false;
        if(state and cost < ans)    ans = cost;   
    }

    if(ans != INF)
        cout << ans;
    else    cout << -1;
}

Measured memory_bytes: 3656
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input! {
        n: usize,
        s: chars,
        k: usize1,
    }
    let mut st = String::new();
    for i in 0..n {
        if s[i] == s[k] {
            st.push(s[k].clone());
        } else {
            st.push('*');
        }
    }
    println!("{}", st);
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <cstdio>
#include <math.h>
#include <utility>
#include <list>
#include <functional>
using namespace std;

#define ll long long
#define vecint vector<int>
#define Pii pair<int, int>

#define REP(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define print(a) cout << a << endl

#define MOD 1000000007
#define NIL -1

ll x,y;

void solve(){
  if(abs(x-y)>=2){
    print("Alice");
  }else{
    print("Brown");
  }
  return;
}

int main(){
  cin>>x>>y;
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int x, p; cin >> x >> p;
  cout << fixed << setprecision(15) << 50.0 * (x + (x & 1)) / p << '\n';
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  function<vector<int>(int)> getPrimes = [&](int x) {
    vector<int> ret;
    vector<bool> vis(x + 1);
    for (int k = 2; k <= x; ++k)
      if (!vis[k]) {
        ret.push_back(k);
        for (int j = k; j <= x; j += k)
          vis[j] = true;
      }
    return ret;
  };
  vector<int> pr = getPrimes(2200);
  vector<ll> pr3;
  for (int p : pr) pr3.push_back(p * (ll)p * p);

  int N;
  cin >> N;
  map<ll, int> cnt;
  int ans = 0;
  ll mx = 0;
  while (N--) {
    ll x;
    cin >> x;
    for (ll v : pr3)
      while (x % v == 0)
        x /= v;
    if (x == 1)
      ans = 1;
    else
      ++cnt[x];
    mx = max(mx, x);
  }
  function<int(ll)> pSQRT = [&](ll x) {
    int rt = sqrt(x);
    while (rt * (ll)rt < x) ++rt;
    while (rt * (ll)rt > x) --rt;
    return rt * (ll)rt == x ? rt : -1;
  };
  function<ll(ll)> dual = [&](ll x) {
    ll fact = 1;
    for (int p : pr)
      if (x % p == 0) {
        if (x / p % p == 0) {
          x /= p * p;
          fact *= p;
        } else {
          x /= p;
          fact *= p;
          if (fact > mx)
            return -1LL;
          fact *= p;
        }
        if (fact > mx)
          return -1LL;
      }
    int cur = pSQRT(x);
    if (cur == -1) {
      if (fact * x > mx / x)
        return -1LL;
      return fact * x * x;
    }
    return fact * cur;
  };

  while (!cnt.empty()) {
    ll x;
    int a;
    tie(x, a) = *cnt.begin();
    cnt.erase(cnt.begin());
    ll du = dual(x);
    ans += max(cnt[du], a);
    cnt.erase(du);
  }
  cout << ans;

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


Measured memory_bytes: 7936
N,M = map(int,input().split())
r = [[0,10],[10,100],[100,1000]]
y = []
for _ in range(M):
    s,c = map(int,input().split())
    y.append([s,c])

ans = -1
for i in range(r[N-1][0],r[N-1][1]):
    p = True
    num = list(str(i))
    for j in range(M):
        if num[y[j][0]-1] != str(y[j][1]):
            p = False
            break
    if p == True:
        ans = i
        break

print(ans)

Measured memory_bytes: 3064
/**
 * File    : A.cpp
 * Author  : Kazune Takahashi
 * Created : 2018-11-8 19:57:07
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <functional>
#include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725));
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

int main()
{
  int A[4];
  cin >> A[0] >> A[1] >> A[2] >> A[3];
  cout << min(A[0], A[1]) + min(A[2], A[3]) << endl;
}

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

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  
  int count = 0;
  for (int i = 0; i < N - 2; i++) {
    if (S.at(i) == 'A') {
      if (S.at(i + 1) == 'B') {
        if (S.at(i + 2) == 'C') {
          count++;
        }
        else {
          continue;
        }
      }
      else {
        continue;
      }
    }
    else {
      continue;
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main()
 {
  char s[100];
  scanf("%[^\n]",s);
  if (s[0] == s[1] && s[2] == s[3] && s[0] != s[2] ||
  s[0] == s[2] && s[1] == s[3] && s[0] != s[1]||
  s[0] == s[3] && s[1] == s[2] && s[0] != s[1])
  {
    printf("Yes\n");
  }
  else
 {
    printf("No\n");
 }
  return 0;
}


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

int main(){
    int N,K,l[60];
    cin>>N>>K;
    for(int i=0;i<N;i++){
        cin>>l[i];
    }
    sort(l,l+N,greater<int>());
    int ans=0;
    for(int i=0;i<K;i++){
        ans=ans+l[i];
    }
    cout<<ans<<endl;
}



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

int main()
{
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    int d = max(a,max(b,c));
    int m = d*pow(2.0,k);
    cout << a+b+c-d+m << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
   int n,i,j,k,s;
   scanf("%d%d%d",&n,&k,&s);
   if(n!=k)
   {
      for(i=1;i<=k;i++)
	  	 printf("%d ",s);
	  if(s==1000000000)
	  {
	  for(i=1;i<n-k;i++)
	  	 printf("%d ",s-10);
	  	 printf("%d",s-10);
}
      else 
      {
      	for(i=1;i<n-k;i++)
      	 printf("%d ",s+1);
	  	 printf("%d",s+1);
	  }
}
   else 
   {
   	for(i=1;i<n;i++)
   	printf("%d ",s);
   	printf("%d",s);
   }
   return 0;
}

Measured memory_bytes: 1280
/* AOJ 0058 Orthogonal */

#include <stdio.h>
#include <math.h>

int
main(void)
{
    double xA, yA, xB, yB, xC, yC, xD, yD;

    while (scanf("%lf%lf%lf%lf%lf%lf%lf%lf",
                 &xA, &yA, &xB, &yB, &xC, &yC, &xD, &yD) != EOF) {
        if (fabs((xB - xA) * (xD - xC) + (yB - yA) * (yD - yC)) < 1e-10)
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}

Measured memory_bytes: 612
nk=input().split()
total=set(range(1,int(nk[0])+1))
mina=set()
for r in range(int(nk[1])):
    D=int(input())
    A=list(map(int,input().split()))
    mina=mina|set(A)
anser=total-mina
print(len(anser))

Measured memory_bytes: 9132
#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;



typedef pair < long long, long long > pll;
typedef unsigned long long ull;
typedef pair < int, int > pii;
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;
typedef long long ll;
typedef double db;
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 511;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 466;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;

int x[6];

main () {
	for (int i = 1; i <= 5; ++i) {
		cin >> x[i];
		if (!x[i])
			cout << i << endl; 
		}

}



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

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
typedef long long ll;

using namespace std;

#define MAX_N 1000000

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll a, b;
	char s;
	while (1) {
		cin >> a >> s >> b;
		if (s == '?') break;
		switch (s)
		{
		case '+':
			cout << a + b << endl;
			break;
		case '-':
			cout << a - b << endl;
			break;
		case '*':
			cout << a * b << endl;
			break;
		case '/':
			cout << a / b << endl;
			break;
		default:
			break;
		}
	}
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
#define endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

int n;

void read()
{
	cin >> n;
}

void solve()
{
	for(int k = 1; k <= 2000; k++)
	{
		int sum = 0;
		for(int p = k; p >= 1; p--)
			sum += 2 * (p - 1);
	
		if(sum == 2 * n)
		{
			cout << "Yes" << endl;
			cout << k << endl;
			
			vector<vector<int> > ret;
			ret.assign(k, vector<int>());

			int v = 1;
			for(int p = k; p >= 1; p--)
			{
				int curr = k - p;
				for(int o = 0; o < (p - 1); o++)
				{
					ret[curr].push_back(v);
					ret[curr + o + 1].push_back(v++);
				}
			}

			for(auto it: ret)
			{
				cout << it.size() << " ";
				for(int x: it)
					cout << x << " ";
				cout << endl;
			}
			return;
		}
	}


	cout << "No" << endl;
}

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

	read();
	solve();
	return 0;
}



Measured memory_bytes: 2304
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().execute();
	}

	public void execute() {
		Scanner sc = new Scanner(System.in);
		final long N = sc.nextLong();
		long minFab = Integer.MAX_VALUE;

		for (int i = 1, cap = (int) Math.sqrt(N) + 1; i <= cap; i++) {
			long a = i;
			if (N % a == 0) {
				long b = N / i;
				minFab = Math.min(minFab, F(a, b));
			}
		}
		System.out.println(minFab);
		sc.close();
	}

	private int F(long a, long b) {
		return Math.max(Long.toString(a).length(), Long.toString(b).length());
	}
}


Measured memory_bytes: 23124
def cmb(n, r):
    if n <= 0 or n < r:
        return 0
    if n == r or r == 0:
        return 1
    if r == 1:
        return n
    return cmb(n-1,r-1) + cmb(n-1,r)
def main():
    n, m = map(int, input().split())
    a = cmb(n, 2)
    a += cmb(m, 2)
    print(a)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template <typename T>
struct SegmentTree {
    int n;
    vector<T> node;
    T calc(T a, T b) {
        return a + b;
    }
    T e = 0;
    SegmentTree(vector<T> v) {
        int sz = v.size();
        n = 1;
        while (n < sz) {
            n *= 2;
        }
        node.resize(2 * n - 1, e);
        for (int i = 0; i < sz; i++) {
            node[i + n - 1] = v[i];
        }
        for (int i = n - 2; i >= 0; i--) {
            node[i] = calc(node[2 * i + 1], node[2 * i + 2]);
        }
    }
    SegmentTree(T sz) {
        n = 1;
        while (n < sz) {
            n *= 2;
        }
        node.resize(2 * n - 1, e);
    }
    void update(int x, T val) {
        x = n + x - 1;
        node[x] = val;
        while (x > 0) {
            x = (x - 1) / 2;
            node[x] = calc(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    void add(int x, T val) {
        x = n + x - 1;
        node[x] += val;
        while (x > 0) {
            x = (x - 1) / 2;
            node[x] = calc(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    T query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return e;
        if (a <= l && r <= b) return node[k];
        T vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        T vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return calc(vl, vr);
    }
    T at(int x) {
        return node[n + x - 1];
    }
};
int main() {
    int n, q;
    cin >> n >> q;
    SegmentTree<ll> segt(n);
    while (q--) {
        int com;
        cin >> com;
        if (com) {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            cout << segt.query(x, y + 1) << endl;
        } else {
            int x;
            ll y;
            cin >> x >> y;
            x--;
            segt.add(x, y);
        }
    }
}



Measured memory_bytes: 4884
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<pair<int, int>> ab(n);
    rep(i, n) cin >> ab[i].first >> ab[i].second;
    sort(all(ab));
    cout << ab[n - 1].first + ab[n - 1].second << endl;
    return 0;
}


Measured memory_bytes: 1024
n,m,q = map(int, input().split())

import itertools
a = []
for i in range(q):
    a.append(input().split())

suma = sum([int(aa[3]) for aa in a])

ans = 0
l = [i for i in range(m)]
for v in itertools.combinations_with_replacement(l, n-1):
    ans_ = 0
    v = [0]+list(v)
    for j in range(q):
        if v[int(a[j][1])-1] - v[int(a[j][0])-1] == int(a[j][2]):
            ans_ += int(a[j][3])
    if ans_ > ans:
        ans = ans_
        if ans == suma:
            break
print(ans)

Measured memory_bytes: 9160
#include <iostream>
#include <utility>
#include <stdint.h>

using namespace std;

int main()
{
  int N, W;
  cin >> N >> W;

  uint32_t Weight[N+1], Value[N+1];
  uint64_t dp[N+1][W+1];

  for (int n=1; n<=N; ++n)
    cin >> Weight[n] >> Value[n];

  for (int n=0; n<=N; ++n)
    dp[n][0] = 0;
  for (int w=0; w<=W; ++w)
    dp[0][w] = 0;

  for (int n=1; n<=N; ++n) {
    for (int w=1; w<=W; ++w) {
      if (w >= Weight[n])
	dp[n][w] = max(dp[n-1][w], dp[n-1][w-Weight[n]] + Value[n]);
      else
	dp[n][w] = dp[n-1][w];
    }
  }

  cout << dp[N][W] << endl;

  return 0;
}


Measured memory_bytes: 79104
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;


int n;
ll x;
ll a[105];

int main(void){
	scanf("%d%lld",&n,&x);
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a,a+n);
	int cnt=0;
	bool flag=false;
	for(int i=0;i<n;i++){
		if(a[i]<=x){
			x-=a[i];
			cnt++;
		}else{
			flag=true;
		}
	}
	if(x>0 && cnt>0 && !flag)cnt--;
	printf("%d\n",cnt);
	return 0;
} 

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, 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 fractions import gcd
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 = 10 ** 9 + 7

N = INT()
A = INT()
print("Yes" if N%500 <= A else "No")

Measured memory_bytes: 5144
import sys
import itertools
import numpy as np

MOD = 998244353
MAX = 10 ** 5 * 2 + 5

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

def com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

comInit(MOD)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n, m, k = map(int, readline().split())

ans = 0
col = m
for x in range(n - 1, -1, -1):
    now = col
    now *= com(n - 1, x, MOD) % MOD
    if x <= k:
        ans += now
    col = (col * (m - 1)) % MOD

print(ans % MOD)

Measured memory_bytes: 50888
from collections import deque

H, W = map(int, input().split())
s = [input() for _ in range(H)]

adj = [[] for _ in range(W*H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0

for i in range(H):
    for j in range(W):
        if s[i][j] == '#': continue
        ans += 1
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if 0 <= y < H and 0 <= x < W:
                if s[y][x] == '.':
                    adj[W*i + j].append(W*y + x)

queue = deque([0])
visit = [-1] * (H*W)
visit[0] = 1

while queue:
    now = queue.popleft()
    for u in adj[now]:
        if visit[u] < 0:
            queue.append(u)
            visit[u] = visit[now] + 1

print(ans - visit[H*W-1]) if visit[H*W-1] > 0 else print(-1)

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

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

    int n, x;
    cin >> n >> x;
    vector<int> A(n);
    REP(i, n) cin >> A[i];

    sort(A.begin(), A.end());
    int cnt = 0;
    REP(i, n){
        if(x - A[i] >= 0){
            x -= A[i];
            cnt++;
        }else{
            break;
        }
    }

    //xが0より多いということは誰かに押し付ける必要がある
    //押し付け先は必ず満足しないことになる
    //全員が満足している場合は誰か犠牲に
    //そうでない場合は満足してないマンに押し付ければ満足する人数は変わらない
    if(x > 0 and cnt == n){
        cnt--;
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int m,n;
string s;
bool b[1001];

int main(){
	while(cin>>m>>n){
		if(!m)return 0;
		int c=1,p=m;
		fill(b,b+m+1,0);
		for(int i=1;i<=n;i++){
			//cout<<"player "<<c<<":"<<endl;
			cin>>s;
			if(!(i%15)){
				if(s!="FizzBuzz"){b[c]=1;p--;}
				//else cout<<"s"<<endl;
			}
			else if(!(i%3)){
				if(s!="Fizz"){b[c]=1;p--;}
				//else cout<<"s"<<endl;
			}
			else if(!(i%5)){
				if(s!="Buzz"){b[c]=1;p--;}
				//else cout<<"s"<<endl;
			}
			else{
				int f=0;
				if(s.size()<6){
					int cur=0,N=0;
					while(cur<s.size()){
						if(!isdigit(s[cur])){f=2;break;}
						N=N*10+s[cur++]-'0';
					}
					if(!f&&N==i)f=1;
				}
				if(f!=1){b[c]=1;p--;}
				//else cout<<"s"<<endl;
			}
			if(p==1){for(int j=i+1;j<=n;j++)cin>>s;break;}
			c++;
			if(c==m+1)c=1;
			while(b[c]){c++;if(c==m+1)c=1;}
		}
		int f=0;
		for(int i=1;i<=m;i++){
			if(!b[i]){
				if(f)cout<<" ";
				cout<<i;
				f=1;
			}
		}
		cout<<endl;
	}
}

Measured memory_bytes: 924