akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N,W;
ll dp[100*1000+5];
ll max(ll a, ll b){
	if(a>b) return a;return b;
}

// dp[w][i] = max(dp[w-wt[i]][i-1]+v[i], dp[w][i-1])

// dp[v] = min(wt[i] + dp[v-V[i]], dp[v])
ll wt[100+5], V[100+5];

ll MAXV = 1;
int main(){
	cin>>N>>W;
	for(int i = 0;i<N;i++){
		cin>>wt[i]>>V[i];
		MAXV+=V[i];
	}
	
	for(ll j = 0;j<=MAXV;j++) 
		dp[j] = 1e18;
	
	dp[0] = 0;
	for(ll i = 0;i<N;i++){
		for(ll v = MAXV;v>=V[i];v--){
			dp[v] = min(dp[v], wt[i]+dp[v-V[i]]);
		}
	}
	ll ans = 0;
	for(ll v = MAXV;v>=1;v--){
		if(dp[v]<=W){
			ans = v;break;
		}
	}
	
	cout<<ans<<endl;
}


Measured memory_bytes: 1024
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		String[] a = new String[h];
		for (int i = 0; i < h; i++) {
			a[i] = sc.next();
		}

		boolean[] row = new boolean[h];
		Arrays.fill(row, false);
		boolean[] col = new boolean[w];
		Arrays.fill(col, false);
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (a[i].charAt(j) == '#') {
					row[i] = true;
					col[j] = true;		//1つでもあったらその列業は圧縮不可能
				}
			}
		}

		for (int i = 0; i < h; i++) {
			if (row[i]) {
				for (int j = 0; j < w; j++) {
					if (col[j]) {
						System.out.print(a[i].charAt(j));
					}
				}
				System.out.println();
			}
		}
	}
}


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

#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << " = " << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define SP << " " <<

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vec;
typedef vector<P> pvec;
typedef vector<vector<int>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<int> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<int,vector<int>,greater<int>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;

const vector<int> DX = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> DY = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const ll INF = (1LL << 60); // 1152921504606846976
const double PI = (3.141592653589794);
const double EPS = (0.0000000001); // 10^(-10)

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> inline T ceil(T a, T b) {return T((a + b - 1) / b);}
template<class T> inline T round(T a, T b) {return T(a / b);}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
template <class T> inline void out(T &a) { bool flag=true; for(auto&x:a){if(flag) {flag=false;} else{ cout << ' '; } cout<<x; } cout << endl; }



//----------------------------------------------------------------
int nmax=200000; // 2*(10^5)
vvec G(nmax);





void solve4ts()
{
    
    
    int x,y;
    cin>>x>>y;
    int yy=0;
    for(int i=0;i<1000;i++){
        for(int j=0;j<1000;j++){
            if(i*2+j*4==y&&i+j==x){
                yy++;
            }
        }
    }
    if(yy==0){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
    }
}
//-----------------------------------------------------------------

signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15);
    int repeat = 1;
    // cin >> repeat;
    while(repeat--) solve4ts();
}

Measured memory_bytes: 7816
#include <cstdio>
#include <algorithm>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

using ll = long long;

ll N;
ll A[100010];
ll dp[100010][2];

int main()
{
  scanf( "%lld", &N );
  rep( i, N )
    scanf( "%lld", A+i );

  dp[0][0] = A[0], dp[0][1] = -A[0];

  rep( i, N )
  {
    dp[i+1][0] = std::max( dp[i][0]+A[i+1], dp[i][1]-A[i+1] );
    dp[i+1][1] = std::max( dp[i][0]-A[i+1], dp[i][1]+A[i+1] );
  }

  printf( "%lld\n", dp[N-1][0] );

  return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
int a[maxn];
long long dp[maxn],sum[maxn];
int main(){
	int n,i;
	cin>>n; 
	for(i=1;i<=n;i++)
		cin>>a[i];
	for(i=1;i<=n;i++)
		if(i%2)
			sum[i]=sum[i-1]+a[i];
		else
			sum[i]=sum[i-1];
	for(i=2;i<=n;i++)
		if(i%2)
			dp[i]=max(dp[i-2]+a[i],dp[i-1]);
		else 
			dp[i]=max(dp[i-2]+a[i],sum[i-1]);
	cout<<dp[n]<<endl;
	return 0;
}

Measured memory_bytes: 7500
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <utility>

#define reps(i,s,n) for(long long (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

int main(){
    int N;
    cin >> N;
    ll w=0;

    reps(n,1,3510){
        reps(h,1,3510){
            ll t1 = (ll)N*h*n;
            ll t2 = (ll)(4*h*n - N*n - N*h);
            if(t2 > 0 ){
                if(t1 % t2 == 0){
                    w = t1 / t2;
                    cout << h << " " << n << " " << w << endl;
                    return 0;
                }
            }
        }
    }


    return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
 
int main() 
{
  int n, m;
  cin >> n >> m;
  
  int sd[n][2], cp[m][2];
  
  for (int i = 0; i < n; i++)
    cin >> sd[i][0] >> sd[i][1];
  
  for (int j = 0; j < m; j++)
    cin >> cp[j][0] >> cp[j][1];
  
  
  for (int i = 0; i < n; i++) {
    
    int temp[2] = {0, 0};
    
    for (int j = 0; j < m; j++) {
      int dist = 
        abs(cp[j][0] - sd[i][0]) + abs(cp[j][1] - sd[i][1]);
      
      if (j == 0) {
        temp[0] = dist;
        temp[1] = 1;
      }
      else {
        if (temp[0] > dist) {
          temp[0] = dist;
          temp[1] = j + 1;
        }
      }
    }
    
    cout << temp[1] << endl;
  }
}

Measured memory_bytes: 3600
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
int main(void)
{
	int i,j,n,max,mx;
	int flg[10001];
	while(1) {
		scanf("%d",&n);
		if(n==0) break;
		for(i=2;i<=n;i++) flg[i]=1;
		for(i=2;i*i<=n;i++) {
			if(flg[i]==1) for(j=2;j*i<=n;j++) flg[i*j]=0;
		}
		max=-1;
		for(i=n;i>=5;i--)	{
			if(flg[i]==1 && flg[i-2]==1)	break;
		}
		max=i-2;
//		for(i=2;i<n;i++) {
//			if(flg[i]==1 && flg[i]==flg[i+2] && i+2<=n) {
//				if(max<i) max=i;
//			}
//		}
		printf("%d %d\n",max,max+2);
	}
	return 0;
}
		

Measured memory_bytes: 1064
#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll H,W;
int main(){
    cin>>H>>W;
    ll ans=min((H%3!=0)*W,(W%3!=0)*H);
    for(ll i=1;i<H;i++){
        ll mi=min({(W+1)/2*(H-i),W/2*(H-i),i*W});
        ll ma=max({(W+1)/2*(H-i),W/2*(H-i),i*W});
        ans=min(ma-mi,ans);
    }
    for(ll i=1;i<W;i++){
        ll mi=min({(H+1)/2*(W-i),H/2*(W-i),i*H});
        ll ma=max({(H+1)/2*(W-i),H/2*(W-i),i*H});
        ans=min(ma-mi,ans);
    }
    cout<<ans;
    return 0;
}

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

signed main() {
	int n, m, ma = 0;
	cin >> n >> m;
	for (int i = 1; i*i <= m; i++) {
		if (m%i == 0 && m / i >= n) {
			ma = max(ma, i);
		}
		if (m%i==0&&m/(m/i)>=n){
			ma = max(ma, m / i);
		}
	}
	cout << ma << endl;

	END;
}


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

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

  int ans=1000000;
  
  for (int j=0; j<100; j++){
    int t_ans=0;
    for (int k=0; k<n; k++){
      t_ans+=(j-x[k])*(j-x[k]);
    }
    ans=min(ans,t_ans);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
n = int(input())
l = list(map(int, input().split()))
l.sort()

def bin_search(x, ok, ng, l):
    while ng - ok > 1:
        mid = (ng + ok) // 2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok + 1

ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        ans += bin_search(l[i] + l[j], -1, n - j - 1, l[j + 1:])
print(ans)

Measured memory_bytes: 51804
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 1000003
q = int(input())
cumprod = [1]
for i in range(1, MOD):
	cumprod.append((cumprod[-1] * i) % MOD)

def calc(l, r):
	return (cumprod[r] * pow(cumprod[l-1], MOD-2, MOD)) % MOD

def solve(x, d, n):
	if x == 0:
		return 0
	elif d == 0:
		return pow(x, n, MOD)
	else:
		l = (x * pow(d, MOD-2, MOD)) % MOD
		if l+n-1 >= MOD:
			return 0
		else:
			return (calc(l, l+n-1) * pow(d, n, MOD)) % MOD

for _ in range(q):
	x, d, n = map(int, input().split())
	print(solve(x, d, n))

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

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  long long ans=0,sum=0;
  for(int i=0;i<N;++i) cin >> A.at(i);
  for(int i=0;i<N;++i){
    B.at(i)=A.at(i)-(i+1);
  }
  sort(B.begin(),B.end());
  int b=B.at(N/2);
  for(int i=0;i<N;++i) ans+=abs(A.at(i)-b-(i+1));
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, K;
    cin >> N >> K;
    deque<int> value(N);
    for(int i = 0; i < N; i++) cin >> value.at(i);
    
    int R = min(N, K);
    int ans = 0;
    for(int A = 0; A <= R; A++) {
        for(int B = 0; B <= R-A; B++) {
            int tmp = 0;
            
            deque<int> copy_value(N);
            for(int i = 0; i < N; i++) copy_value.at(i) = value.at(i);
            
            vector<int> temochi;
            for(int i = 0; i < A; i++) {
                temochi.push_back(copy_value.front());
                copy_value.pop_front();
            }
            for(int i = 0; i < B; i++) {
                temochi.push_back(copy_value.back());
                copy_value.pop_back();
            }
            
            sort(temochi.begin(), temochi.end());
            int i = 0;
          	int s = temochi.size();
            while(i < min(K-A-B, s) && temochi.at(i) < 0){
                temochi.at(i) = 0;
                i++;
            }
            
            for(int i = 0; i < temochi.size(); i++) {
                tmp += temochi.at(i);
            }
            ans = max(ans, tmp);
        }
    }
  
  	cout << ans << endl;
}


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

#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
struct Grid{int x,y,t;};
struct Edge{int to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=1010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(int from,int to,int cost){E[from-1].pb({to-1,cost});}
};
int main(){
  int n;cin>>n;
  vector<ll>a(n+10);
  ll sum[n+1]={};
  for(int i=0;i<n+1;i++)sum[i]=0;
  ll dp[n+1][n+1]={};
  for(int i=0;i<n+1;i++)for(int j=0;j<n+1;j++)dp[i][j]=llINF;
    for(int i=1;i<=n;i++){cin>>a[i];dp[i][i]=0;sum[i]+=sum[i-1]+a[i];}
    for(int i=2;i<=n;i++){
      for(int j=1;j<=n-i+1;j++){
	for(int k=1;k<i;k++){
	  dp[j][j+i-1]=min(dp[j][j+i-1],min(dp[j][j+k-1]+dp[j+k][j+i-1],dp[j][j+i-1-k]+dp[j+i-k][j+i-1]));
	}
	dp[j][j+i-1]+=(sum[j+i-1]-sum[j-1]);
      }
    }
    cout<<dp[1][n]<<endl;
  return 0;
}


Measured memory_bytes: 1536
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

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

const int MX=100005;

int main()
{
    int x;
    cin>> x;
    int y=8,r=599;
    while(x>r) y--,r+=200;
    cout<< y <<endl;
    return 0;
}

Measured memory_bytes: 3616
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long a[100005];
int n;
long long sum;
int cot;
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)scanf("%I64d", &a[i]);
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; i++)
	{
		sum += a[i];
		if(sum * 2 >= a[i + 1])cot++;
		else cot = 0;
	}
	printf("%d\n", cot);
}

Measured memory_bytes: 896
#include<iostream>
#include<cstring>
using namespace std;
char s[5];
int main() 
{
    cin>>s+1;
    if((s[1]==s[2])&&(s[3]==s[4])&&(s[1] != s[3]))
        cout<<"Yes";
    else if((s[1]==s[3])&&(s[2]==s[4])&&(s[1]!=s[2]))
        cout<<"Yes";
    else if((s[1]==s[4])&&(s[2]==s[3]&&(s[1]!=s[2])))
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ff first
#define ss second
const ll mod = 1e9 + 7 ;
ll multiply(ll a, ll b){ return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b) {     return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a%mod) - (b % mod)+ mod) % mod ; }
///////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////
void solve( ){
    ll n , k ;
    cin >> n >> k ;
    vector < ll > a(n) ;
    for( int i = 0 ; i < n ; i++) cin >> a[i] ;
    sort(a.begin(),a.end());
    int r = max((ll)0,n-k);
    ll sum = 0 ;
    for( int i = 0 ; i < r ; i++) sum+= a[i] ;
    cout << sum ;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test_case=1 ;
    //cin >> test_case ;
    for( int i = 1 ; i <= test_case ; i++){
        solve( );
    }
}


Measured memory_bytes: 1792
x, n = map(int,input().split())
p = list(map(int,input().split()))
p_list = [0 for i in range(100)]
n_abs = 1000
ans = 100000

for i in p:
    p_list[i-1] = 1

for i in range(0, 102):
    if i == 0 or i == 101:
        temp_abs = abs(x-i)
        if n_abs > temp_abs:
            n_abs = temp_abs
            ans = i
    else:
        temp_abs = abs(x-i)
        if n_abs > temp_abs and p_list[i-1] != 1:
            n_abs = temp_abs
            ans = i
        elif n_abs == temp_abs and i < ans and p_lsit[i-1] != 1:
            n_abs = temp_abs
            ans = i

print(ans)


Measured memory_bytes: 8984
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
long long a[200005];
int main()
{
	int n;
	cin >> n;
	memset(a, 0, sizeof(a));
	for (int i = 0; i < n; i++)
	{
		scanf("%lld", &a[i]);
	}
	int i = 0;
	long long ans = 0;
	for (int i = 0; i < n-1; i++)
	{
		if (a[i] > a[i + 1])
		{
			long long k = a[i];
			while (k > a[i + 1] && i < n-1)
			{
				ans += k - a[i + 1];
				i++;
			}
		}
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 5300
#include <stdio.h>
#include <map>
#include <string>

using namespace std;

#define REP(i, n) for (int i = 0; i < n; ++i)

struct data_t {
    int blue_card_cnt;
    int red_card_cnt;
};

int main() {
    // 青いカード
    int N;
    scanf("%d", &N);

    map<string, data_t> m;
    REP(i, N) {
        char str[11];
        scanf("%s", str);

        map<string, data_t>::iterator it = m.find(str);
        if (it != m.end()) {
            m[str].blue_card_cnt++;
        } else {
            m.insert(make_pair(str, (data_t){1, 0}));
        }
    }

    // 赤いカード
    int M;
    scanf("%d", &M);

    REP(i, M) {
        char str[11];
        scanf("%s", str);

        map<string, data_t>::iterator it = m.find(str);
        if (it != m.end()) {
            m[str].red_card_cnt++;
        } else {
            m.insert(make_pair(str, (data_t){0, 1}));
        }
    }


    int ans = 0;
    for (map<string, data_t>::iterator it = m.begin(); it != m.end(); ++it) {
        ans = max(ans, (it->second).blue_card_cnt - (it->second).red_card_cnt);
        /*
        printf(
            "%s: %d - %d = %d\n",
            (it->first).c_str(),
            (it->second).blue_card_cnt,
            (it->second).red_card_cnt,
            (it->second).blue_card_cnt - (it->second).red_card_cnt
        );
        */
    }

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

    return 0;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <cstring>
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <numeric>
#include <float.h>
using namespace std;
// repマクロの定義
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// allマクロの定義
#define all(v) v.begin(), v.end()
typedef unsigned long long ll;

/* 最大公約数求める関数
auto my_gcd(auto n , auto m){
  if(n < m){
    auto tmp = n;
    n = m;
    m = tmp;
  }
  auto l  = n % m;
  while(l != 0){
    n = m;
    m = l;
    l = n % m;
}
return m;
}

//char⇒int関数
 int ctoi(char c) {
 	switch (c) {
		case '0': return 0;
		case '1': return 1;
		case '2': return 2;
		case '3': return 3;
		case '4': return 4;
		case '5': return 5;
		case '6': return 6;
		case '7': return 7;
		case '8': return 8;
		case '9': return 9;
		default: return 0;
	}
}
*/


int main(){
string s; cin >> s;
  stack<int> S;
  rep(i,s.size()){
	  if(s[i] == '0'){
		  S.push(0);
	  }
	  else if(s[i] == '1'){
		  S.push(1);
	  }
	  else{
		  if(! S.empty()){
			  S.pop();
		  }
	  }
  }
  vector<int> A(S.size());
  int k = S.size();
for(int i = k-1; i >= 0; i--){
	A[i] = S.top();
	S.pop();
}

	for(int i = 0; i< k ;i++){
		cout << A[i];
	}

	cout << endl;
  }


Measured memory_bytes: 3580
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

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







signed main(){
    int n,q;
    cin>>n>>q;
    char str[n];
    rep(i,n)cin>>str[i];
    int hint[n];
    for(int i=1;i<n;i++){
        if(str[i]=='C'&&str[i-1]=='A')
            hint[i]=1;
        else
            hint[i]=0;
    }
    int dp[n];
    dp[0]=0;
    for(int i=1;i<n;i++){
        dp[i]=dp[i-1]+hint[i];
       
    }
    for(int i=0;i<q;i++){
        int ans=0;
        int l,r;
        cin>>l>>r;
        ans=dp[r-1]-dp[l-1];
        cout<<ans<<endl;
    
    }
    
}

Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
const long long INF=1LL<<60;

int main(){
  int n;
  cin >> n;
  vector<long long> a(n);
  for(int i=0;i<n;++i){
    cin >> a[i];
  }
  int N=(int)a.size();
  vector<long long> dp(N,INF);
  for(int i=0;i<N;++i){
    *lower_bound(dp.begin(),dp.end(),a[i])=a[i];
  }

  cout << lower_bound(dp.begin(),dp.end(),INF)-dp.begin();
  cout << endl;
  return 0;
}



Measured memory_bytes: 4408
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int INF = 1000000007;
using ll = long long;
using namespace std;
using P = pair<int, int>;
int main() {
    int n, m;
    cin >> n >> m;
    vector<P> v1, v2;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        v1.emplace_back(x, y);
    }
    for (int j = 0; j < m; ++j) {
        int x, y;
        cin >> x >> y;
        v2.emplace_back(x, y);
    }
    for (auto &&v : v1) {
        int k = INF, z = 0;
        int x = v.first, y = v.second;
        for (int i = 0; i < m; ++i) {
            int x1 = v2[i].first, y1 = v2[i].second;
            if(abs(x1-x) + abs(y1-y) < k) z = i+1, k = abs(x1-x) + abs(y1-y);
        }
        cout << z << "\n";
    }

    return 0;
}


Measured memory_bytes: 256
n=int(input())
cnt=[[0]*10 for _ in range(10)]
#print(cnt)
for i in range(1,n+1):
    tmp=str(i)
    a=int(tmp[0])
    b=int(tmp[-1])
    cnt[a][b]+=1

sum=0
for i in range(1,10):
    for j in range(1, 10):
     sum+=cnt[i][j]*cnt[j][i]

print(sum)   

Measured memory_bytes: 3064
#include<cstdio>

int main(){
    int m,f,r;
    for(int i = 0; i < 50; i++){
        scanf("%d %d %d",&m,&f,&r);
        int s;
        if(m == -1 && f == -1 && r == -1){
            break;
        }
        s = m + f;
        if(m == -1 || f == -1){
            printf("F\n");
        }
        else if(s >= 80){
            printf("A\n");
        }
        else if(s >= 65 && s < 80){
            printf("B\n");
        }
        else if(s >= 50 && s < 65){
            printf("C\n");
        }
        else if(s >= 30 && s < 50){
            if(r >= 50){
                printf("C\n");
            }
            else{
                printf("D\n");
            }
        }
        else if(s < 30){
            printf("F\n");
        }
    }
}


Measured memory_bytes: 2620
while True:
    n,x = map(int,input().split())
    if n == 0 and x == 0:
        break
    c = 0
    for i in range(1,n+1):
        for k in range(1,i):
            for j in range(1,k):
                a = i + k + j
                if a == x:
                    if i != k != j:
                        c += 1
    print(c)


Measured memory_bytes: 5592
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=400010;
char s[maxn];
ll ans,n,f[maxn];

int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
		f[s[i]-'a']++;	
	ans=n*(n+1)/2;
	for(int i=0;i<=25;i++)
		ans-=f[i]*(f[i]+1)/2;	
	printf("%lld",ans+1);	
	return 0;
}

Measured memory_bytes: 384
def read_input():
    a, b = map(int, input().split())
    return a, b


def check_palindromic(x):
    s = str(x)
    rev = s[::-1]
    return s == rev


def submit():
    a, b = read_input()

    count = 0
    for i in range(a, b+1):
        if check_palindromic(i):
            count += 1

    print(count)

if __name__ == '__main__':
    submit()


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

int main()
{
  int N;
  cin >> N;
  if(N == 1)
  {
    cout << "Hello World" << endl;
  }
  else
  {
    int A, B;
    cin >> A >> B;
    cout << A + B << endl;
  }
}


Measured memory_bytes: 256
def main():
  n = int(raw_input())
  sticks = list(sorted(map(int, raw_input().split())))
  result = 0

  for x in xrange(n):
      z = x + 2
      for y in xrange(x+1, n):
          while (z < n and sticks[x] + sticks[y] > sticks[z]):
              z += 1
          result += z - y -1
  print(result)

main()


Measured memory_bytes: 2692
N = int(input())
A = input()

A = A.split()

lst = []



for i in range(N):
	c = 0
	a = int(A[i])
	while  a % 2 == 0:
		a = a / 2
		c = c + 1
	lst.append(c)
	
anc = lst[0]
	
for i in range(1, N):
	if anc > lst[i]:
		anc = lst[i]
		
print(anc)

Measured memory_bytes: 3064
#include <set>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	multiset <int> s;
	int n,m,tmp;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>tmp;
		s.insert(tmp);
	}
	cin>>m;
	multiset <int> ::iterator it; 
	for(int i=1;i<=m;i++){
		cin>>tmp;
		if(s.find(tmp)!=s.end()){
			it=s.find(tmp);
			s.erase(it);
		}
		else {cout<<"NO"<<endl;return 0;}
	}
	cout<<"YES"<<endl;
	return 0;
}

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const LL mod = 1e9+7;

vector<vector<LL>> mul(vector<vector<LL>> &a, vector<vector<LL>> &b, int N){
	vector<vector<LL>> c(N,vector<LL>(N,0));
	repp(i,0,N) repp(j,0,N) repp(k,0,N) (c[i][k] += a[i][j]*b[j][k]) %= mod;
	return c;
}

int main(){
	int N; LL K; cin >> N >> K;
	vector<vector<LL>> a(N,vector<LL>(N)),z(N,vector<LL>(N,0));
	repp(i,0,N) repp(j,0,N) cin >> a[i][j];
	repp(i,0,N) z[i][i] = 1;
	while(K){
		if(K&1) z = mul(z,a,N);
		a = mul(a,a,N);
		K /= 2;
	}
	LL ans = 0;
	repp(i,0,N) repp(j,0,N) (ans += z[i][j]) %= mod;
	cout << ans << endl;
	return 0;
}


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

bool check(int x);

int main(void){
    // Your code here!
    int x,a,b,c,count = 0;
    cin >> a >> b >> c >> x;
    if(!check(x)){
        cout << "Error" << endl;
        return 0;
    }
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(x == (500*i+100*j+50*k)) count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

bool check(int x){
    if(x%50 == 0) return true;
    return false;
}

Measured memory_bytes: 256
#include <stdio.h>
char a[10000][100000];
int main ()
{
	int h,w,i,j;
	scanf ("%d%d",&h,&w);
	for (i=0;i<h;i++)
	{
			scanf ("%s",&a[i]);
	}
	for (i=0;i<w+1;i++)
	{
		printf ("#");
	}
	printf ("#\n");
	for (i=0;i<h;i++)
	{
		printf ("#");
		for (j=0;j<w;j++)
		{
			printf ("%c",a[i][j]);
		}
		printf ("#\n");
	}
	for (i=0;i<w+1;i++)
	{
		printf ("#");
	}
	printf ("#\n");
	return 0;
}


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

#define ed cout << "\n";
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ffor(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(i, n) ffor(i, 0, n)
#define All(obj) (obj).begin(), (obj).end()
#define INF ((ll)1e9 + 7)
#define c(a) cout << a << "\n";
using namespace std;
const int N = 100005;

int main()
{
    speed;
    cout << fixed << setprecision(6);
    /*start*/
    int n, k;
    cin >> n >> k;
    vector<ll> h(n);
    rep(i, n) cin >> h[i];
    sort(All(h));
    rep(i, k)
    {
        h.pop_back();
    }
    ll sum = 0;
    rep(i, n - k)
    {
        sum += h[i];
    }
    c(sum);
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int mx = 212345;
const long long inf = 0x3f3f3f3f3f3f3f3f;

typedef pair<long long, int> E;

int arr[mx];

int root(int x) {
  return x == arr[x] ? x : arr[x] = root(arr[x]);
}

void join(int a, int b) {
  a = root(a);
  b = root(b);
  if(a == b) return;
  arr[a] = b;
}

int U[mx];
pair<int, int> best[mx];

long long f(int a, int b, int D) {
  return 1LL * abs(a-b) * D + U[a] + U[b];
}

int n;

E t1[2*mx], t2[2*mx];

void update(E t[], int p, E value) { // set value at position p
  for(t[p += n] = value; p > 1; p >>= 1) t[p>>1] = min(t[p], t[p^1]); // Merge
}

E query(E t[], int l, int r) {
  E res = {inf, -1};
  for(l += n, r += n+1; l < r; l >>= 1, r >>= 1) {
    if(l&1) res = min(res, t[l++]); // Merge
    if(r&1) res = min(res, t[--r]); // Merge
  }
  return res;
}

vector<int> G[mx];

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int m, D;
  cin >> n >> D;
  for (int i = 0; i < n; i++) {
    cin >> U[i];
  }
  
  /*
  vector<pair<int, pair<int, int>>> v;
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      v.push_back({f(i, j, D), {i, j}});
    }
  }
  sort(v.begin(), v.end());
  iota(arr, arr+n, 0);
  for (int i = 0; i < v.size(); i++) {
    int a = v[i].y.x;
    int b = v[i].y.y;
    if(root(a) == root(b)) continue;
    cout << a << " " << b << " " << v[i].x << endl;
    join(a, b);
  }
  cout << endl;
  */
  int ntrees = n;
  for (int i = 0; i < n; i++) {
    update(t1, i, E{1LL * i * D + U[i], i});
    update(t2, i, E{1LL * (n-1-i) * D + U[i], i});
  }
  iota(arr, arr+n, 0);
  long long ans = 0;
  while (ntrees > 1) {
    
    
    for(int i = 0; i < n; i++) G[i].clear(), best[i] = {-1, -1};
    for(int i = 0; i < n; i++) {
      G[root(i)].push_back(i);
    }
    
    for(int i = 0; i < n; i++) {
      for (auto a: G[i]) {
        update(t1, a, E{inf, a});
        update(t2, a, E{inf, a});
      }
      for (auto a: G[i]) {
        E r1 = query(t1, a+1, n-1);
        r1.x += -1LL*a*D + U[a];
        E r2 = query(t2, 0, a-1);
        r2.x += -1LL*(n-1-a)*D + U[a];
        
        E r = min(r1, r2);
        int b = r.y;
        if(b == -1) continue;
        if (best[root(a)].x == -1 || f(best[root(a)].y, best[root(a)].x, D) > r.x) best[root(a)] = {a, b};
        if (best[root(b)].x == -1 || f(best[root(b)].y, best[root(b)].x, D) > r.x) best[root(b)] = {a, b};
      }
      for (auto a: G[i]) {
        update(t1, a, E{1LL * a * D + U[a], a});
        update(t2, a, E{1LL * (n-1-a) * D + U[a], a});
      }
    }
    for (int i = 0; i < n; i++) {
      if (~best[i].x) {
        int a = best[i].x, b = best[i].y;
        int c1 = root(a), c2 = root(b);
        if(c1 == c2) continue;
        ans += f(a, b, D);
        join(c1, c2);
        ntrees--;
      }
    }
  }
  cout << ans << endl;
}

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

using namespace std;

const long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}
long long fast_exp(long long base, long long exp, long long mod = MOD) {
    long long tot = 1;
    for(;exp > 0;exp >>= 1) {
       if((exp & 1) == 1) tot = tot * base % mod;
       base = base * base % mod;
    }
    return tot;
}

vector<int> adj[100005];
int state[100005];

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, a, b; cin >> n;

    for(int i = 1; i < n; ++i){
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        state[i] = -1;
    }

    state[1] = 1;

    queue<pair<int, int>> q;
    q.push(make_pair(1, 1));
    q.push(make_pair(n, 0));

    int whi = 0, bla = 0;

    while(!q.empty()){
        int node = q.front().first, col = q.front().second;
        q.pop();
        col == 1 ? ++bla : ++whi;
        for(int nx : adj[node]){
            if(state[nx] != -1) continue;
            state[nx] = col;
            q.push(make_pair(nx, col));
        }
    }

    cout << (bla > whi ? "Fennec\n" : "Snuke\n");

    return 0;

}


Measured memory_bytes: 6400
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let N: usize = sc.get();
    let mut p = Vec::new();
    for _ in 0..N {
        let x: i64 = sc.get();
        let y: i64 = sc.get();
        p.push((x, y));
    }
    let mut cnt = HashMap::new();
    for i in 0..N {
        let (x1, y1) = p[i];
        for j in 0..N {
            if i == j {
                continue;
            }
            let (x2, y2) = p[j];
            let (dx, dy) = (x2 - x1, y2 - y1);
            let e = cnt.entry((dx, dy)).or_insert(0);
            *e += 1;
        }
    }
    let mut max = 0;
    for (_, &num) in &cnt {
        if max < num {
            max = num;
        }
    }
    let ans = N - max;
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <stdio.h>

int main(){
  int a,b,A[10000],B[10000],count=0,i,j;
  scanf("%d",&a);
  for(i=0;i<a;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&b);
  for(i=0;i<b;i++){
    scanf("%d",&B[i]);
  }
   
  for(i=0;i<b;i++){
    for(j=0;j<a;j++){
      if(A[j]==B[i]){
count++;
break;
}
    }
  }
  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 644
#define _USE_MATH_DEFINES

#include <iostream>
#include <algorithm> // min()
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <stack>
#include <tuple>
#include <random>

#include <climits> // INT_MAX
#include <cmath> // ceil()
#include <cstring>

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

const int type_num = 26;
int D;
vector<ll> c(type_num);
vector<vector<ll>> s;
//vector<ll> satis_hist;

ll decrease_satis(vector<int>& last, ll d) {
	ll y = 0;
	rep(i, type_num) y += c[i] * (d + 1 - last[i]);
	return y;
}


ll calc_satis(vector<int>& t) {
	ll satis = 0;
	vector<int> last(type_num);
	rep(i, D) {
		last[t[i]] = i + 1;
		satis += s[i][t[i]] - decrease_satis(last, i);
		//satis_hist[i] = satis;
	}
	return satis;
}

int main() {
	cin >> D;

	rep(i, type_num) cin >> c[i];

	//vector<ll> t(D);
	rep(i, D) {
		vector<ll> temp(type_num);
		rep(j, type_num) {
			cin >> temp[j];
		}
		//auto iter = max_element(b2e(temp));
		//size_t index = distance(temp.begin(), iter);
		//t[i] = index;
		s.emplace_back(temp);
	}

	vector<int> t(D);
	rep(i, D) {
		cin >> t[i];
		t[i]--;
	}

	//auto satis = calc_satis(t);

	ll M;
	cin >> M;
	vector<pair<int, int>> dq(M);
	rep(i, M) {
		ll _d, _q;
		cin >> _d >> _q;
		dq[i] = make_pair(_d-1, _q-1);
	}

	rep(i, M) {
		t[dq[i].first] = dq[i].second;
		cout << calc_satis(t) << endl;
	}

}

Measured memory_bytes: 3808
#スタック用の配列を用意する
S =[]

lis = list(map(str, input().split()))

for sub in lis:
    if sub in ['+','-','*']:
        b = int(S.pop())
        a = int(S.pop())
        #sub が+であった場合
        if sub == '+':
            S.append(a+b)
        if sub == '-':
            S.append(a-b)
        if sub == '*':
            S.append(a*b)
    else:
        S.append(sub)
print("%d"%(S[0]))


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

using vi=vector<int>;
using vvi=vector<vector<int>>;

int main(){
  int n;cin>>n;
  vi v(n),x(n-1);
  int sum=0;
  rep(i,n)cin>>v[i];
  rep(i,n){
    int a;cin>>a;
    sum+=a;
  }
  rep(i,n-1)cin>>x[i];
  rep(i,n-1){
    if(v[i]+1==v[i+1])sum+=x[v[i]-1];
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
from collections import defaultdict


def main():
    N, P = map(int, input().split())
    S = input()
    ans = 0
    if P in [2, 5]:
        for i, d in enumerate(S[::-1]):
            if int(d) % P == 0:
                ans += N - i
    else:
        total = defaultdict(int)
        total[0] = 1
        cur = 0
        for i, d in enumerate(S[::-1]):
            d = int(d) % P
            prev = cur
            cur = (prev + pow(10, i, P) * d) % P
            ans += total[cur]
            total[cur] += 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 43708
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


typedef long long LL;


const int N = 1000010;

const LL mod = 1000000007LL;


#define L first
#define R second


LL Plus(LL a, LL b) { return a + b >= mod ? a + b - mod : a + b; }


struct Frenwick_Tree
{	LL C[N]; int sz;

	void upd(int x, LL v) { for (int i = x; i <= sz; i += i & (-i)) C[i] = Plus(C[i], v); }

	LL getSum(int x)
	{	LL Ans = 0;
		for (int i = x; i > 0; i -= i & (-i)) Ans = Plus(Ans, C[i]);
		return Ans;
	}
} Calc;

pair<int, int> num[N];
int dis[N];
int total[2];

bool cmp(pair<int, int> & a, pair<int, int> & b) { return a.L != b.L ? a.L < b.L : a.R > b.R; }


int a[N], b[N];

LL f[N];

int main()
{	int n, m;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	
	for (int i = 1; i <= m; i++)
		scanf("%d", &b[i]);
	
	for (int i = 1; i <= n; i++)
	{	if (a[i] > b[1] && a[i] < b[m])
		{	int pos = lower_bound(b + 1, b + 1 + m, a[i]) - b;
			if (b[pos] != a[i])
			{	num[++total[0]] = make_pair(a[i] - b[pos - 1], b[pos] - a[i]);
				dis[++total[1]] = b[pos] - a[i];
			}
		}
	}
	
	sort(dis + 1, dis + total[1] + 1);
	total[1] = unique(dis + 1, dis + total[1] + 1) - dis - 1;
	
	for (int i = 1; i <= total[0]; i++)
		num[i].R = lower_bound(dis + 1, dis + total[1] + 1, num[i].R) - dis;
	
	sort(num + 1, num + total[0] + 1, cmp);
	total[0] = unique(num + 1, num + total[0] + 1) - num - 1;
	
	LL Ans = 1;
	
	Calc.sz = total[1];
	
	for (int i = 1; i <= total[0]; i++)
	{	f[i] = Calc.getSum(num[i].R - 1) + 1;
		Ans = Plus(Ans, f[i]);
		Calc.upd(num[i].R, f[i]);
	}
	
	printf("%lld\n", Ans);
	
	return 0;
}

Measured memory_bytes: 13312
#include<bits/stdc++.h>
#define lld         long long int
#define llf         long double
#define pb          push_back
#define mp          make_pair
#define IN          insert
#define loopN(n)    for(lld i=0;i<n;i++)
#define loop(p,n)   for(lld i=p;i<=n;i++)
#define rloop(p,n)  for(lld i=n;i>=p;i--)
#define loop2(p,n)  for(lld j=p;j<=n;j++)
#define all(v)      v.begin(),v.end()
#define F1          first
#define F2          second
#define INF         2e18
#define FILE        freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
#define PI          2*acos(0.0)
#define ISO         ios::sync_with_stdio(false);cin.tie(0)
#define mem(a,b)    memset(a,b,sizeof(a))
#define case(z)     cout<<"Case "<<z<<": ";
using namespace std;
const lld mod=1e9+7;
lld n,mw;
lld w[105],v[105];
lld dp[105][100005];

lld fun(lld p,lld k)
{
    if(k<=0)
    {
        return 0;
    }
    if(p>=n)
    {
        return 0;
    }
    if(dp[p][k]!=-1)
    {
        return dp[p][k];
    }
    if(k>=w[p])
    {
        return dp[p][k]=max(v[p]+fun(p+1,k-w[p]),fun(p+1,k));
    }
    else
    {
        return dp[p][k]=fun(p+1,k);

    }



}

int main()
{
    ISO;

    //lld t;cin>>t;while(t--)
    mem(dp,-1);
    cin>>n>>mw;
    loopN(n)cin>>w[i]>>v[i];
    cout<<fun(0,mw)<<endl;

    return 0;
}



Measured memory_bytes: 85608
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
vector<int> tobit(ll k, ll n) {
    vector<int> res(n, 0);
    for(int i = 0; i < n; i++) {
        res[i] = k % 2;
        k /= 2;
    }
    return res;
}
int main() {
    int n, m, x;
    cin >> n >> m >> x;
    vector<ll> c(n, 0);
    vector<vector<ll>> a(n, vector<ll>(m, 0));
    for(int i = 0; i < n; i++) {
        cin >> c[i];
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    ll ans = LLONG_MAX;
    for(int k = 0; k < (1 << n); k++) {
        auto v = tobit(k, n);
        ll tmp = 0;
        vector<ll> sc(m, 0);
        for(int i = 0; i < n; i++) {
            if(v[i]) {
                tmp += c[i];
                for(int j = 0; j < m; j++) {
                    sc[j] += a[i][j];
                }
            }
        }
        if(*min_element(all(sc)) >= x) {
            ans = min(ans, tmp);
        }
    }
    if(ans != LLONG_MAX) {
        cout << ans << endl;
    } else {
        cout << -1 << endl;
    }
}

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

// Optimization

//#pragma GCC optimize("O3")
#define endl '\n'

// Shortcut

#define int long long
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define Ford(i, r, l) for (int i = r; i > l; i--)
#define FordE(i, r, l) for (int i = r; i >= l; i--)
#define Fora(i, a) for (auto i : a)

// I/O & Debug

#define PrintV(a) Fora(iiii, a) cout << iiii << ' '; cout << endl;
#define PrintVl(a) Fora(iiii, a) cout << iiii << endl;
#define PrintA(a, l, r) for (int iiii = l; iiii <= r; iiii++) cout << a[iiii] << ' '; cout << endl;
#define PrintAl(a, l, r) for (int iiii = l; iiii <= r; iiii++) cout << a[iiii] << endl;
#define Ptest(x) return cout << x, 0;
#define gl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
/*
#define debug(args...){ string _sDEB = #args; replace(_sDEB.begin(), _sDEB.end(), ',', ' '); stringstream _ssDEB(_sDEB); istream_iterator<string> _itDEB(_ssDEB); DEB(_itDEB, args); }
void DEB(istream_iterator<string> it) {}
template<typename T, typename... Args>
void DEB(istream_iterator<string> it, T a, Args... args){
    cout << *it << " = " << a << endl;
    DEB(++it, args...);
}
*/

// Functions

//#define isvowel(a) (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
#define bend(a) a.begin(), a.end()
#define rbend(a) a.rbegin(), a.rend()
#define mset(a) memset(a, 0, sizeof(a))
#define mset1(a) memset(a, 1, sizeof(a))
#define msetn1(a) memset(a, -1, sizeof(a))
#define msetinf(a) memset(a, 0x3f, sizeof(a))
#define gcd __gcd
#define __builtin_popcount __builtin_popcountll
//mt19937 rando(chrono::steady_clock::now().time_since_epoch().count());

// Data Structure

#define pque priority_queue
#define mts multiset
#define y0 _y0_
#define y1 _y1_
#define div divi
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <ld> vld;
typedef vector <string> vs;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <vi > vvi;
typedef vector <vll > vvll;
typedef vector <pii > vpii;
typedef vector <pll > vpll;

const int N = 2e5 + 5, mod = 1e9 + 7, mod1 = 998244353, mod2 = 1e9 + 9, inf = 1e9 + 7;
const ll infll = 1e18 + 7;

int n, m, k;
int x, y, z;
int ans, cnt, tmp, idx, val, sum, mx = -inf, mn = inf;
string s, t;
int a[N], b[N];
set <int> stt; map <string, int> mpp;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    while (n--){
        cin >> s; mpp[s]++;
    }
    cout << mpp.size();
}

/*
==================================+
INPUT:                            |
------------------------------    |

------------------------------    |
==================================+
OUTPUT:                           |
------------------------------    |

------------------------------    |
==================================+
*/

Measured memory_bytes: 19244
#define ll long long int
#include <bits/stdc++.h>
//#include <fstream>
using namespace std;
 
#define         ff               first
#define         ss               second
#define         mp               make_pair
#define         pb               push_back
#define         pf               push_front
#define         vi               vector<ll>
#define         pii              pair<ll,ll>
#define         qi               queue<ll>
#define         mem(a,b)         memset(a,b,sizeof(a))
#define         print(a)         cout<<a<<'\n'
#define         sorted(arr)      sort(arr.begin(),arr.end())
#define         gcd(a,b)         gcd((a),(b))
#define         lcm(a,b)         ((a)*(b))/gcd((a),(b))
#define         all(v)           v.begin(),v.end()
#define         read(a)          scanf("%d", &a)
#define         f(a,n)           for(ll i=a;i<n;i++)
#define         in2(n,m,arr)     for(ll i=0;i<n;i++){for(ll j=0;j<m;j++)cin>>arr[i][j];}
#define         debug(a)         cerr<<a<<" ";
#define         debug1(a)        cerr<<a<<'\n'
 
/*typedef tree<int, null_type, less<int>, rb_tree_tag , tree_order_statistics_node_update> Set;*/
 
 
const unsigned ll mod = 1e9 + 7 ;
const ll inf = (ll)1e18 + 2;
const ll N = (ll)1e6 + 2;
//
//template<typename... T>
//void write(T&... args)
//{
//    ((cout << args << ' '), ...);
//}
//ll power ( ll x , ll y)
//{
//    ll res = 1;
//    while (y > 0)
//    {
//        if (y & 1)
//            res = (res * x) ;
//        y = y >> 1;
//        x = (x * x) ;
//    }
//    return res  ;
//}
//
//struct node{
//    ll x , y , z;
//};
//map<pair<ll, ll>,ll> c;
//vector<set<ll>> tree;
//vector<ll> ar ;
//set<ll> s;
//ll get(ll x)
//{
//    if(x == ar[x])
//        return x;
//    return ar[x] = get(ar[x]);
//}
//void merge(ll a ,ll b)
//{
//    a = get(a);
//    b = get(b);
//    if(a == b)
//    {
//        return ;
//    }
//    ar[b] = ar[a];
// }
//
//ll sev[100006];
//vector<ll> pri;
//void seive()
//{
//    for(ll i = 2 ; i < 100006 ; i ++)
//    {
//        if(!sev[i])
//        {
//            for(ll j = i ; j < 100006 ; j += i)
//            {
//                if(!sev[j])
//                    sev[j] = i;
//            }
//        }
//        if(sev[i] == i)
//            pri.pb(i);
//    }
//}
vector<vector<ll>> graph;
ll visi[N] , mx = 0;
ll nodes[N];
map<pii , ll> vis;
void bfs(ll idx)
{
    visi[idx] = 1;
    for(auto x : graph[idx])
    {
        if(!visi[x])
          bfs(x);
        nodes[idx] = max(nodes[idx] , nodes[x] + 1);
        
    }
    return;
}
void solve()
{
    ll n , m , a , b;
    cin >> n >> m;
    graph.resize(n);
    for(ll i = 0 ; i < m ; i ++)
    {
        cin >> a >> b;
        a -- , b --;
        graph[a].pb(b);
    }
    for(ll i = 0 ; i < n ; i ++)
    {
        if(!visi[i])
            bfs(i);
    }
    for(ll i = 0 ;i < n ; i ++)
        mx = max(mx , nodes[i]);
    print(mx);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t ;
    t = 1;
    //cin >> t;
    //seive();
    while(t --)
    {
        solve();
    }
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
 


Measured memory_bytes: 12672