akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,weight,c;
vector<ll> wei,val;
long long q[101][100002];
ll dp(ll ind,ll weil){
    if(ind<0||weil<=0) return 0;
        if(q[ind][weil]!=0) return q[ind][weil];
    if(wei[ind]>weil) q[ind][weil]=dp(ind-1,weil);
    else q[ind][weil]=max(dp(ind-1,weil),val[ind]+dp(ind-1,weil-wei[ind]));
    return q[ind][weil];
}
int main(){
cin>>n>>weight;
for(ll i=0;i<n;i++){
    cin>>c;
    wei.push_back(c);
    cin>>c;
    val.push_back(c);
}
cout<<dp(n-1,weight)<<'\n';
return 0;
}


Measured memory_bytes: 74960
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long
#define pb push_back
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inp(n) for(i=0;i<n;i++) cin>>A[i];
#define inz(A) memset(A,0,sizeof(A))
#define lb lower_bound
#define ub upper_bound
#define all(v) v.begin(),v.end()
#define T 1000000
#define F first
#define S second
#define pi pair<int,int>
#define vi vector<int>v;
#define sz(v) v.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define forn(i,a,b) for(int i=a;i<=b;i++)
			/*brownsands IIITA*/

signed main(){
  		
                boost
		int n,w,i,j;
  cin>>n>>w;
  int weight[n+1],value[n+1];
  
  for(i=0;i<n;i++)
    cin>>weight[i]>>value[i];
  int knap[n+1][w+1];
                inz(knap);
                for(i=1;i<=n;i++){
                    for(j=1;j<=w;j++){
                        if(weight[i-1]<=j){
                            knap[i][j]=max(value[i-1]+knap[i-1][j-weight[i-1]],knap[i-1][j]);
                        }
                        else
                        knap[i][j]=knap[i-1][j];
                    }
                }
  
  cout<<knap[n][w];
  }
 

				
		
		





Measured memory_bytes: 79232
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
ll num[11];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,m; cin >> n >> m;
  vector<ll> sw[n];
  rep(i,m){
      ll k;cin >> k;
      rep(j,k){
          ll s;
          cin >> s;
          s--;
          sw[s].push_back(i);
      }
  }
  vector<ll> p(m);
  rep(i,m){
      cin >> p[i];
  }
  ll ans = 0;
  rep(i,(1<<n)){
      rep(j,n){
          if((i>>j)&1){
              rep(k,sw[j].size()){
                  num[sw[j][k]]++;
              }
          }
      }
      bool isok = true;
      rep(j,m){
          if(num[j]%2 != p[j])isok = false;
      }
      if(isok)ans++;
      rep(j,m){
          num[j]=0;
      }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int h,w,i,j;

  scanf("%d%d",&h,&w);

  while(h!=0 || w!=0){
    for(j=0;j<w;j++)  printf("#");
    printf("\n");
    for(i=1;i<h-1;i++){
      printf("#");
      for(j=1;j<w-1;j++)  printf(".");
      printf("#\n");
    }
    for(j=0;j<w;j++)  printf("#");
    printf("\n\n");
    scanf("%d%d",&h,&w);
  }

  return 0;
}

Measured memory_bytes: 588
def main():
    N = int(input())
    V = list(map(int, input().split()))
    while len(V) > 1:
        V.sort()
        new_v = sum(V[0:2]) / 2
        V = V[2:]
        V.append(new_v)
    print(V[0])


if __name__ == '__main__':
    main()


Measured memory_bytes: 61744
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define iii tuple<int, int, int>
#define ii pair<int, int>
#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void solve() {
    int n, M = 1e9 + 7;
    cin >> n;

    vector<vector<int>> a(n, vector<int>(n));

    for (auto& i : a)
        for (auto& j : i) cin >> j;

    vector<int> dp(1 << n), cnt(1 << n), step(1 << n);
    dp[0] = 1;

    int s = 0, t = 1;
    while (s + 1 < (1 << n)) {
        int msk = step[s++], i = cnt[msk];

        if (i == n) break;

        for (int j = 0; j < n; ++j) {
            if (a[i][j] && !(msk & (1 << j))) {
                if (!cnt[msk | (1 << j)]) {
                    step[t++] = msk | (1 << j);
                    cnt[msk | (1 << j)] = cnt[msk] + 1;
                }
                dp[msk | (1 << j)] = (dp[msk | (1 << j)] + dp[msk]) % M;
            }
        }
        dp[msk] = 0;
    }
    cout << dp[(1 << n) - 1] << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // freopen("in", "r", stdin);

    int t = 1;
    // cin >> t;
    while (t--) solve();

    return 0;
}

Measured memory_bytes: 24832
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define yn(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YN(ans) if(ans)printf("YES\n");else printf("NO\n")
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }

int main(){
    int n;
    in(n);
    vector<int> vec(n);
    in(vec);
    ll ans=0;
    for(int i=0;i<n;i++){
        if(i+1<n){
            ans+=(ll)vec[i]/2;
            vec[i]-=2*(vec[i]/2);
            //要検討
            if(vec[i]==1&&vec[i+1]>=1){
                ans++;
                vec[i]--;
                vec[i+1]--;
            }
        }else if(i==n-1){
            ans+=(ll)vec[i]/2;
            vec[i]-=vec[i]/2;
        }
    }
    out(ans);
}

Measured memory_bytes: 3788
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

  private void run() {

    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int heapSize = Integer.parseInt(br.readLine());
      String[] keys = br.readLine().split(" ");
      int[] mHeap = new int[heapSize+1];
      mHeap[0] = heapSize;
      for(int i=1; i<=heapSize; i++)
        mHeap[i] = Integer.parseInt( keys[i-1] );

      buildMaxHeap(mHeap);

      StringBuilder buf = new StringBuilder();
      for(int i=1; i<mHeap.length; i++) 
        buf.append(" ").append(mHeap[i]);

      System.out.println(buf);
    } catch(IOException e) {
      System.out.println("IOException!");
    }
  }
  private void buildMaxHeap(int[] heap) {
    for(int i= heap[0]/2; i>0; i--)
      maxHeapify(heap, i);
  }
  private void maxHeapify(int[] heap, int node) {
    int t,left,right,largest;
    left  = node*2;
    right = left+1;

    if( (left <= heap[0]) && (heap[left] > heap[node]) )
      largest = left;
    else
      largest = node;
    if( (right <= heap[0]) && (heap[right] > heap[largest]) )
      largest = right;

    if( largest != node ) {
      t = heap[node]; heap[node] = heap[largest]; heap[largest] = t;

      maxHeapify(heap, largest);
    }
  }
}


Measured memory_bytes: 75420
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
int main(){
	int h,w;cin>>h>>w;
	string s;
	rep(i,h){
		cin>>s;
		cout<<s<<endl;
		cout<<s<<endl;
	}
}

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

int par[1000005],sum[1000005];

int find(int x){
  if(x==par[x])return x;
  int t=find(par[x]);
  sum[x]+=sum[par[x]];
  par[x]=t;
  return par[x];
}

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<=n;i++)
    par[i]=i;
  while(m--){
    int a,b,c,p,q,s;
    cin>>a>>b>>s;
    p=find(a),q=find(b);
    if(p==q){
      if(abs(sum[b]-sum[a])!=s){
        cout<<"No";
        return 0;
      }
    }
    else{
      par[p]=q;
      sum[p]=s+sum[b]-sum[a];
    }
  }
  cout<<"Yes";
  return 0;
}

Measured memory_bytes: 4864
#include <stdio.h>
#include <string.h>
int n, m, d[100005];
char s[100005];
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	d[0] = 1;
	for (int i = 5; i <= n; i++) {
		if (d[i - 5] && s[i - 4] == 'd' && s[i - 3] == 'r' && s[i - 2] == 'e' && s[i - 1] == 'a' && s[i] == 'm') d[i] = 1;
		if (d[i - 5] && s[i - 4] == 'e' && s[i - 3] == 'r' && s[i - 2] == 'a' && s[i - 1] == 's' && s[i] == 'e') d[i] = 1;
		if (d[i - 7] && s[i - 6] == 'd' && s[i - 5] == 'r' && s[i - 4] == 'e' && s[i - 3] == 'a' && s[i - 2] == 'm' && s[i - 1] == 'e' && s[i] == 'r') d[i] = 1;
		if (d[i - 6] && s[i - 5] == 'e' && s[i - 4] == 'r' && s[i - 3] == 'a' && s[i - 2] == 's' && s[i - 1] == 'e' && s[i] == 'r') d[i] = 1;
	}
	if (d[n]) puts("YES");
	else puts("NO");
}

Measured memory_bytes: 640
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true)
        {
            int x = sc.nextInt();
            int y = sc.nextInt();
            if(x == 0 && y == 0)
                break;
            if(x > y)
            {
                int tmp = x;
                x = y;
                y = tmp;
            }
            System.out.println(x + " " + y);
        }
    }
}


Measured memory_bytes: 35628
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <string>
using namespace std;
 
int check(vector<int> v, int n){
  int a=v[0];
  for(int i=1;i<n;i++){
    if(a!=v[i])a=v[i];
    else{
      return 0;
    }
  }
  return 1;
}

int main() {
	cin.tie(0);
  ios::sync_with_stdio(false);
 
	int n;
  vector<int> v;
  cin>>n;
  for(int i=0; i<n; i++){
    int tmp;
    cin>>tmp;
    v.push_back(tmp);
  }
  sort(v.begin(),v.end());
  if(check(v,n) == 0)cout<<"NO";
  else{
    cout<<"YES";
  }
  

  return 0;
}

Measured memory_bytes: 1908
/*
  ∧,,∧
( 'ω' )つ ＜WA,またお前か！！　
（m9 ＼ 　　
　 ＼　 ＼
　 　 ) ) ＼
　 ／／ ＼ ＼
　 (＿） 　 (＿)
*/

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

#define all(x) (x).begin(),(x).end()

typedef long long LL;
typedef long double LD;

bool compare_by_a(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return a.second < a.second;
    }
}

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

int func(int n) {
    if (n % 2 == 0) return n/2;
    else return 3*n + 1;
}

int main()
{
    int s;
    cin >> s;
    int temp;
    vector<int> a(1, s);

    for (int m = 1; m <= 100000; m++) {
        temp = func(a[m-1]);
        a.push_back(temp);
        for (int i = 0; i < m; i++) {
            if (a[i] == temp) {
                cout << m+1 << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
use std::io::Read;
use std::collections::HashSet;
use std::cmp::min;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let s: Vec<char> = iterator.next().unwrap().chars().collect();
    let k: usize = iterator.next().unwrap().parse().unwrap();

    let mut substrings: HashSet<String> = HashSet::new();
    for i in 0..s.len() {
        let mut substring = String::new();
        for j in i..min(s.len(), i + k) {
            substring.push(s[j]);
            substrings.insert(substring.clone());
        }
    }
    let mut substrings: Vec<String> = substrings.clone().into_iter().collect();
    substrings.sort();
    substrings[k - 1].clone()
}


Measured memory_bytes: 5000
n, k = list(map(int, input().split()))
period = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (2*n+1)
dp_cumsum = [0] * (2*n+1)
mod = 998244353

dp[n+1] = 1
dp_cumsum[n+1] = 1

for idx in range(n+2, 2*n+1):
    for l, r in period:
        # dp[idx - r] 〜dp[idx - l]までの和
        dp[idx] += dp_cumsum[idx - l] - dp_cumsum[idx - r - 1]

    dp[idx] %= mod
    dp_cumsum[idx] = (dp_cumsum[idx-1] + dp[idx]) % mod

print(dp[n+n])
# print(dp)
# print(dp_cumsum)



Measured memory_bytes: 27572
import sys
from fractions import gcd

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def lcm(x, y):
    return x * y // gcd(x, y)


def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split(" "))))
    A = [a // 2 for a in A]
    semi_lcm = 1
    for a in A:
        semi_lcm = lcm(semi_lcm, a)
        if semi_lcm > M:
            print(0)
            return

    for a in A:
        if semi_lcm // a % 2 == 0:
            print(0)
            return

    print((M // semi_lcm + 1) // 2)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 13352
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

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

int A,B,C,D;

int main(){
    cin>>A>>B>>C>>D;
    out(max(A*B,C*D));

    
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())

typedef long long ll;
typedef unsigned long long ull;

using namespace std;


int main() {FIN;
    int n;
    string s;
    cin>>n>>s;
    if(n%2!=0) cout<<"No\n";
    else{
        string a,b;
        fore(i,0,n/2) a+= s[i];
        fore(i,n/2,n) b+= s[i];
        if(a == b) cout<<"Yes\n";
        else    cout<<"No\n";
    }
}


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

using namespace std;

//#define MD 1
#define MD 1000000007

int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    sort(v.begin(),v.end());
        if(n%2==1){//奇数人のとき
            int flag=0,tmp=0,sa=2;
            for(int i=1;i<n;i++){
                if(v[0]!=0){
                    cout<<0<<endl;
                    return 0;
                }
                if(v[i]==0){
                    cout<<0<<endl;
                    return 0;
                }
                if(flag==0){
                    tmp=v[i];
                    if(tmp!=sa){
                        cout<<0<<endl;
                        return 0;
                    }
                    flag=1-flag;
                }else{
                    if(tmp==v[i]){
                        flag=1-flag;
                        sa+=2;
                    }else{
                        cout<<0<<endl;
                        return 0;
                    }
                }
            }
            long long int ans=1;
            for(int i=0;i<(n-1)/2;i++){
                ans=((ans % MD)* 2) % MD;
            }
            cout<<ans<<endl;                
        }else{
            int flag=0,tmp=0,sa=1;
            for(int i=0;i<n;i++){
               if(flag==0){
                    tmp=v[i];
                    if(tmp!=sa){
                        cout<<0<<endl;
                        return 0;
                    }
                    flag=1-flag;
                }else{
                    if(tmp==v[i]){
                        flag=1-flag;
                        sa+=2;
                    }else{
                        cout<<0<<endl;
                        return 0;
                    }
                }
            }
             long long int ans=1;
            for(int i=0;i<n/2;i++){
                ans=((ans % MD)* 2) % MD;
            }
            cout<<ans<<endl;     
        }
    
    return 0;
}

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

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

const int maxn=100+10;
const int inf=0x3f3f3f3f;
const ll Inf=1e15;
struct Edge {
	int from,to,nxt;
}e[maxn<<1];
int n;
int tot,Maxd;
int head[maxn],Max[maxn];
pair<int,ll>Ans=make_pair(inf,Inf);

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

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

inline void add(int from,int to) {
	e[++tot]=(Edge){from,to,head[from]}; head[from]=tot;
	e[++tot]=(Edge){to,from,head[to]}; head[to]=tot;
}

void dfs(int u,int fa,int Deep) {
	chkmax(Maxd,Deep);
	int cnt=0;
	for (int i=head[u];i!=0;i=e[i].nxt) {
		int v=e[i].to;
		if (v==fa) continue;
		dfs(v,u,Deep+1); ++cnt;
	}
	chkmax(Max[Deep],cnt);
}

int main() {
//	file();
	n=read();
	For (i,1,n-1) {
		int x=read(),y=read(); add(x,y);
	}
	For (i,1,n) {
		Maxd=0; Set(Max,0); dfs(i,0,1);
		ll ans=1;
		For (j,1,Maxd-1) ans*=(ll)Max[j];
		chkmin(Ans,make_pair(Maxd,ans));
	}
//	printf("%d %lld\n",Ans.first,Ans.second);
	for (int i=1;i<=tot;i+=2) {
		Maxd=0; Set(Max,0);
		dfs(e[i].from,e[i].to,1); dfs(e[i].to,e[i].from,1);
		ll ans=1;
		For (j,1,Maxd-1) ans*=(ll)Max[j];
		chkmin(Ans,make_pair(Maxd,2ll*ans));
	}
	printf("%d %lld",Ans.first,Ans.second);
	return 0;
}

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

using namespace std;

/*

        Bismillahir Rahmanir Rahim
        Problem :
        Problem Link :
        Topics :
        Solver : Masud Parves
        I Love Code More than Sharks Love Blood <3
*/

#define ff first
#define ss second
#define mp make_pair
#define SZ(a)           (int)a.size()
#define all(a)  a.begin(), a.end()
#define allr(a)  a.rbegin(), a.rend()


#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)

#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)

#define CIN ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define TEST_CASE(t) for(int zz=1 ; zz<=t ; zz++)
#define PRINT_CASE printf("Case %d: ",zz)
#define endl            "\n"
#define Debug(x)            cout<<#x " = "<<(x)<<endl
#define NOT_VISITED 0
#define IS_VISITED 1
#define WHITE 0
#define GRAY 1
#define BLACK 2

int fx[4]= {1,-1,0,0};
int fy[4]= {0,0,1,-1};

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N  (1<<pos);}
//int Reset(int N,int pos){return N= N & ~(1<<pos);}
//bool Check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

const double PI = acos(-1.0);
const double EPS = 1e-6;
const int MOD = (int)1e9+7;
const int maxn = (int)3e5+5;


typedef long long ll;
const ll inf = 5e18+100;
typedef unsigned long long ull;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;
typedef vector<int> vi;
int n, a[maxn][4];
ll DP[maxn][4];

ll cal(int pos, int pre){
	if(pos==n){
		return 0LL;
	}

	ll &ret = DP[pos][pre];
	if(ret != -1){
		return ret;
	}

	ret = 0LL;

	for(int i=1 ; i<=3 ; i++){
		if(i==pre) continue;
		ret = max(ret , a[pos][i]+cal(pos+1, i));
	}
	return ret;
}


void solve(){
	cin >> n;

	f0(i, n){
		cin >> a[i][1] >> a[i][2] >> a[i][3];
	}

	memset(DP, -1 , sizeof(DP));

	cout << cal(0, 0) << endl;

    return;
}

int main()
{
    CIN

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    //cout << "Fi Amanillah" << endl;

    int t = 1;
    //cin >> t;

    while(t--){
        solve();
    }

    return 0;
}

Measured memory_bytes: 23916
#include <bits/stdc++.h>
#ifdef DEBUG
#include "_debug.cpp"
#include "callable.hpp/callable.hpp"
#endif
#define endl '\n'
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, a;
    cin >> n >> a;
    cout << (n % 500 <= a ? "Yes" : "No") << endl;
    return 0;
}


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

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }

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

  int N;
  queue<string> que;
  cin >> N;
  que.push("a");
  while (!que.empty()) {
    string s = que.front();
    que.pop();
    if (s.size() == N)
      cout << s << endl;
    else {
      set<char> t;
      rep(i, s.size()) {
        t.insert(s[i]);
      }
      // cout << *(--s.end()) << ' ' << (char)(*(--s.end())+1) << endl;
      t.insert((char)(*(--t.end())+1));
      // for (auto ite = t.begin(); ite != t.end(); ite++)
      //   cout << *ite << ' ';
      // cout << endl;
      for (auto ite = t.begin(); ite != t.end(); ite++) {
        string v;
        v = s + *ite;
        que.push(v);
      }
    }
  }
}


Measured memory_bytes: 9728
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll dp[102][100001];
ll n=0,w=0;
ll weights[102];
ll values[102];
int main() {
    cin>>n>>w;
    for(int i=0;i<102;++i){
        for(int j=0;j<100001;++j){
            dp[i][j]=INT_MAX;
        }
    }
    memset(weights,0,sizeof(weights));
    memset(values,0,sizeof(values));
    ll valuesum=0;
    for(ll i=1;i<=n;++i){
        cin>>weights[i]>>values[i];
        valuesum+=values[i];
    }
    for(int i=0;i<=n;++i)
        dp[i][0]=0;
    for(ll i=1;i<=n;++i){
        for(ll j=1;j<=valuesum;++j){
            if(j<values[i]){
                dp[i][j]=dp[i-1][j];
            }
            else{
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-values[i]]+weights[i]);
            }
        }
    }
    ll ans=0;
    for(ll i=1;i<=valuesum;++i)
        if(dp[n][i]<=w)
            ans=i;
    cout<<ans<<endl;
    return 0;
}


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

int main() {
    int H, W, h, w;
    cin >> H >> W >> h >> w;
    //全体H*WからW*hを引き算し、さらに(H - h)*wを引き算する。
    //(H - h) * (W - w)の展開式と同じになる
    cout << H * W - (W * h + (H - h) * w) << endl;
    return 0;
}

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

string S;
int K;
set<string> S_set;

void abc097c() {
  int n = S.size();
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= min(K, n - i); j++) {
      S_set.insert(S.substr(i, j));
    }
  }
  int cnt = 0;
  for (auto itr = S_set.begin(); itr != S_set.end(); ++itr) {
    if (cnt == K - 1) {
      cout << *itr << "\n";
      return;
    }
    ++cnt;
  }
}

int main() {
  cin >> S >> K;
  abc097c();
  return 0;
}

Measured memory_bytes: 1664
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <vector>
#include <array>
#include <chrono>
#include <random>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
// VAR(int, x);
#define VAR(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__);
template<typename T> void Scan(T& t) { std::cin >> t; }
template<typename First, typename...Rest>void Scan(First& first, Rest&...rest) { std::cin >> first; Scan(rest...); }
#define OUT(d) std::cout<<d;
#define FOUT(n, d) std::cout<<std::fixed<<std::setprecision(n)<<d;
#define SOUT(n, c, d) std::cout<<std::setw(n)<<std::setfill(c)<<d;
#define SP std::cout<<" ";
#define TAB std::cout<<"\t";
#define BR std::cout<<"\n";
#define ENDL std::cout<<std::endl;
#define FLUSH std::cout<<std::flush;
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define MAT(type, c, m, n) std::vector<std::vector<type>> c(m, std::vector<type>(n));for(auto& r:c)for(auto& i:r)std::cin>>i;
#define ALL(a) (a).begin(),(a).end()
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)
#define PAIR std::pair<int, int>
#define IN(a, x, b) (a<=x && x<=b)
#define IN2(a0, y, a1, b0, x, b1) (a0<=y && y<a1 && b0<=x && x<b1)
#define SHOW(d) {std::cout << #d << "\t:" << d << "\n";}
#define SHOWVECTOR(v) {std::cout << #v << "\t:";for(const auto& i : v){std::cout << i << " ";}std::cout << "\n";}
#define SHOWVECTOR2(v) {std::cout << #v << "\t:\n";for(const auto& i : v){for(const auto& j : i){std::cout << j << " ";}std::cout << "\n";}}
#define SHOWPAIRVECTOR2(v) {std::cout << #v << "\t:\n";for(const auto& i : v){for(const auto& j : i){std::cout<<'('<<j.first<<", "<<j.second<<") ";}std::cout << "\n";}}
#define SHOWPAIRVECTOR(v) {for(const auto& i:v){std::cout<<'('<<i.first<<", "<<i.second<<") ";}std::cout<<"\n";}
#define CHECKTIME(state) {auto start=std::chrono::system_clock::now();state();auto end=std::chrono::system_clock::now();auto res=std::chrono::duration_cast<std::chrono::nanoseconds>(end-start).count();std::cerr<<"[Time:"<<res<<"ns  ("<<res/(1.0e9)<<"s)]\n";}

//#define int ll
using ll = long long;
constexpr int INFINT = 1 << 30;
constexpr ll INFLL = 1LL << 60;
constexpr double EPS = 0.0000001;
constexpr int MOD = 1000000007;

signed main() {
	INIT;
	VAR(int, n, l);
	VEC(std::string, s, n);
	std::sort(ALL(s));
	REP(i, n) {
		OUT(s[i]);
	}
	BR;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long int fie[110][11][1100];
int main(){
    while(1){
        memset(fie,0,sizeof(fie));
        int N,S;
        cin>>N>>S;
        if(N==0&&S==0)break;
        fie[1][0][0]=1;fie[1][1][1]=1;
        for(int i=1;i<9;i++){
            for(int j=0;j<10;j++){
                for(int k=0;k<=1000;k++){
                    fie[i+1][j][k]+=fie[i][j][k];
                    fie[i+1][j+1][k+i+1]+=fie[i][j][k];
                }
            }
        }
        cout<<fie[9][N][S]+fie[9][N-1][S]<<endl;
    }
    return 0;
}

Measured memory_bytes: 11556
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,res=0;
	cin >> n;
	int d[n],i;
	for(i = 0; i < n; i++ ) cin >> d[i];
	for(int i = 0; i < n; i++){
		 for(int j = i+1; j < n; j++){
			 res += d[i] * d[j]; 
		 }
	 }
	 cout << res << endl;
 }


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

const int maxn = 200010;
int n, k, p[maxn], f1[20][maxn], f2[20][maxn];

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &p[i]), f1[0][i] = f2[0][i] = p[i];
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j + (1 << i) - 1 < n; j++) {
            f1[i][j] = min(f1[i - 1][j], f1[i - 1][j + (1 << (i - 1))]);
            f2[i][j] = max(f2[i - 1][j], f2[i - 1][j + (1 << (i - 1))]);
        }
    }
    int tot = 1;
    bool flag = 0;
    int cur = 0;
    for (int i = 0; i < k - 1; i++) {
        cur += (p[i] < p[i + 1]);
    }
    if (cur == k - 1) flag = 1, tot = 0;
    for (int i = 1, j = k - 1; i <= n - k; i++) {
        cur -= (p[i - 1] < p[i]);
        cur += (p[j] < p[j + 1]), j++;
        int t = log2(k - 1);
        int mn = min(f1[t][i], f1[t][i + k - 2 - (1 << t) + 1]);
        int mx = max(f2[t][i], f2[t][i + k - 2 - (1 << t) + 1]);
        if (cur == k - 1) { flag = 1; continue; }
        if (p[i - 1] > mn || p[i + k - 1] < mx) tot++;
    }
    printf("%d\n", tot + flag);
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

ll n;
ll a[2002];
bitset<4194304> dp,tmp,one;

int main(){
  cin>>n;
  ll sum=0;
  rep(i,n){
    cin>>a[i];
    sum+=a[i];
  }
  sum=(sum+1)/2;
  dp=1;
  one=1;
  rep(i,n){
    dp|=(dp<<a[i]);
  }
  repl(i,sum,4194304){
    if(((dp>>i)&one)==one){
      cout<<i<<endl;
      return 0;
    }
  }
  return 0;
}


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

int main(){
	int N;
	cin >> N;
	int h[N];
	for(int i=0; i<N; i++){
		cin >> h[i];
	}
	int flag = 0;
	int cnt = 0, b = 0;
	while(1){
		flag = 0;
		b = 0;
		for(int i=0; i<N; i++){
			if(i==0){
				if(h[i] != 0){
					b = 1;
					h[i]--;
					cnt++;
				}
			}else{
				if(b == 0){
					if(h[i] != 0){
						h[i]--;
						b = 1;
						cnt++;
					}
				}else{
					if(h[i] != 0){
						h[i]--;
					}else{
						b = 0;
					}
				}
			}
		}
		for(int i=0; i<N; i++){
			if(h[i] != 0){
				flag = 1;
			}
		}
		if(flag == 0){
			break;
		}
	}
	cout << cnt << endl;
	return 0;
}

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

#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif

signed main(){

  string s; cin >> s;
  int pa = 0,gu = 0,ans = 0;
  for(int i = 0; i < s.size(); i++){
    if(s[i] == 'g'){
      if(gu == pa){
        gu++;
      }
      else {
        pa++;
        ans++;
      }
    }
    else {
      if(gu == pa){
        gu++;
        ans--;
      }
      else {
        pa++;
      }
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
  int n, l;
  vector<string> lines;
  cin >> n >> l;
  for(int i = 0; i < n; i++) {
    string line;
    cin >> line;
    lines.push_back(line);
  }
  sort(lines.begin(), lines.end());
  for(int i = 0; i < n; i++) {
    cout << lines[i];
  }
  cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char a,b;
    scanf("%c",&a);
    getchar();
    scanf("%c",&b);
    getchar();
    if(a<b)printf("<\n");
    else if(a>b)printf(">\n");
    else if(a==b)printf("=\n");
return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Spandan Mishra
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ACirclePond solver = new ACirclePond();
        solver.solve(1, in, out);
        out.close();
    }

    static class ACirclePond {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int r = in.readInt();
            System.out.println(2 * Math.PI * r);

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new RuntimeException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new RuntimeException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }
}



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

using namespace std;

typedef pair<int,int> ii;

const int mod = 1e9+7;

int n,m;
vector<ii> upd[311];
bool ok[311][311][311];
int f[311][311][311];

void init()
{
	memset(ok,true,sizeof true);
	for (int i=0;i<=n;i++)
		for (int j=0;j<=i;j++)
			for (int k=0;k<=j;k++)
			{
				if (i == j && i) continue;
				if (i == k && i) continue;
				if (j == k && j) continue;
				ok[i][j][k] = true;
				for (int h=0;h<upd[i].size();h++)
				{
					int l = upd[i][h].first;
					int cnt = 1;
					if (j >= l) cnt++;
					if (k >= l) cnt++;
					if (cnt != upd[i][h].second)
					{
						ok[i][j][k] = false;
						break;
					}
				} 
			}
}

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

	cin >> n >> m;
	for (int i=1;i<=m;i++)
	{
		int l,r,x;
		cin >> l >> r >> x;
		upd[r].push_back(ii(l,x));	
	}
	init();
	int res = 0;
	f[0][0][0] = 1;
	for (int i=0;i<=n;i++)
		for (int j=0;j<=n;j++)
			for (int k=0;k<=n;k++)
			{
				int x = i, y = j, z = k;
				if (x < y) swap(x,y); if (x < z) swap(x,z); if (y < z) swap(y,z);
				if (!ok[x][y][z]) continue;
				if (x == n) res = (res + f[i][j][k])%mod;
				f[x+1][j][k] = (f[x+1][j][k] + f[i][j][k])%mod;
				f[i][x+1][k] = (f[i][x+1][k] + f[i][j][k])%mod;
				f[i][j][x+1] = (f[i][j][x+1] + f[i][j][k])%mod;
			}
	cout << res;
}

Measured memory_bytes: 144128
#include <bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef long double ld;

const int sz = 10;
ll cnt[sz][sz];


int main(){
	int n; cin >> n;
	for(int i = 1; i<=n; i++){
		string s = to_string(i);
		int d1 = s[0], d2 = s.back();
		cnt[d1-'0'][d2-'0']++;
	}
	ll ans = 0;
	for(int i = 1; i<=n; i++){
		string s = to_string(i);
		int d1 = s[0], d2 = s.back();
		ans+= cnt[d2-'0'][d1-'0'];
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

/* 素因数分解 */
void PrimeFact(ll n,map<ll,ll>& mp){
    while(n!=1){
        if(n == 2 || n == 3){
            mp[n]++; n/=n;
            continue;
        }
        bool prime_flag = false;
        for(ll i = 2;i*i <= n;i++){
            if(n%i==0){
                mp[i]++; n/=i;
                prime_flag = true;
                break;
            }
        }
        if(!prime_flag){mp[n]++; n/= n;}
    }
}

const ll MOD = LLONG_MAX;
ll powmod(ll a,ll b) {ll res=1;a%=MOD;for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}


template<class Type>
Type solve(Type res = Type()){
    ll N,P; cin >> N >> P;
    map<ll,ll> mp;
    PrimeFact(P,mp);
    res = 1;
    for(auto p:mp){
        if(p.second >= N){
            res *= powmod(p.first,p.second/N);
        }
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<ll>() << endl;
    return 0;
}


Measured memory_bytes: 256
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    s = list(input()[:-1].decode())
    ans = 0
    count = 0
    for i in range(len(s)):
        if s[i] == 'W':
            ans += i - count
            count += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T> void operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) cin >> e; }

typedef long long ll;
int const inf = 1<<29;

int main() {
  int a, b ; cin >> a >> b;
  if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
    cout << "Possible\n";
  } else {
    cout << "Impossible\n";
  }
}

Measured memory_bytes: 256
#include <cstdio>
//  A - 9x9

using namespace std;

int main() {
    int A,B;

    scanf("%d%d",&A,&B);

    if (A <= 9 && A >= 1 && B <= 9 && B >= 1)
        printf("%d\n",A * B);
    else
        printf("-1\n");

    return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#include <atcoder/all>

using namespace std;
using namespace atcoder;

#define all(v) (v).begin(),(v).end()
using ll = long long;
constexpr ll INF = 1e18;

int main(void) {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(M), B(M);

    for (ll i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }
    dsu d(N);
    for (ll i = 0; i < M; i++) {
        d.merge(A[i], B[i]);
    }
    cout << d.groups().size() - 1 << endl;
    return 0;
}


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

namespace AtCoder.Contest.A
{
	static class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			Scanner cin = new Scanner();

			int n = cin.NextInt();
			int x = n;
			int ans = 0;
			bool ng = true;
			while (x>0)
			{
				if (x % 10 != 0)
				{
					if (x != 1) ng = false;
				}
				x /= 10;
			}
			if (ng) ans = 10;
			else
			{
				while (n>0)
				{
					ans += n % 10;
					n /= 10;
				}
			}

			Console.WriteLine(ans);

			Console.Out.Flush();
		}
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string Next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return Next();
			i = 0;
			return s[i++];
		}

		public int NextInt()
		{
			return int.Parse(Next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextInt() + add;
			}
			return Array;
		}

		public long NextLong()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextLong() + add;
			}
			return Array;
		}

		public double NextDouble()
		{
			return double.Parse(Next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextDouble() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 11092
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

signed main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(m),b(m);
    rep(i,m)cin>>a[i]>>b[i];
    
    int start = 0;
    rep(i,m)start += a[i]+1;
    
    vector<int> im(n);
    map<pii,int> querys;
    rep(i,m){
        querys[pii(a[i],b[i])]++;
    }
    for(auto elm:querys){
        int A,B,num;
        tie(A,B) = elm.first;
        num = elm.second;
        int pos = B-A-1;
        while(pos<n){
            im[pos] -= B*num;
            pos+=B;
        }
    }
    rep(i,im.size()-1){
        im[i+1] += im[i];
    }
    
    rep(i,n){
        cout<<start+im[i]<<endl;
        start += m;
    }
}



Measured memory_bytes: 11272
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;

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

    pair<ll, int> a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a, a + n);

    ll ans = 0;
    int cou = 0;
    int zou = 0;
    for(int i = 0; i <= n; i++){
        if(cou >= m){
            zou = i - 1;
            break;
        }

        cou += a[i].second;
        ans += (a[i].first * a[i].second);
        //cout << ans << endl;
    }

    //cout << zou << endl;

    if(cou != m){
        while(1){
            if(cou == m){
                break;
            }
            cou--;
            ans -= a[zou].first;
        }
    }

    cout << ans << endl;

}

Measured memory_bytes: 1792
#include <stdio.h>

int main(void)
{
  int cnt = 0;
  int a, b, c;

  scanf("%d %d %d", &a, &b, &c);

  while(a <= b) {
	if (c % a == 0) {
	  cnt++;
	}
	a++;
  }

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

  return 0;
}

Measured memory_bytes: 596
using static System.Math;
using System;

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
         line = Console.ReadLine().Trim().Split(' ');
        var b = Array.ConvertAll(line, int.Parse);
        var rc = 0;   var rmin = int.MaxValue;  var Lmin = int.MaxValue;
        for (int i = 0; i < n; i++)
        {
            if (a[i] == 0) { rc++; rmin = Min(rmin, b[i]); }
            else Lmin = Min(Lmin, b[i]);
        }
        if (rc == 0 | rc == n)  Console.WriteLine(0);
        else Console.WriteLine(rmin + Lmin);
    }
}


Measured memory_bytes: 19968
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	vector<pair<long long, long long>> cnt(N);
	for (int i = 0; i < N; i++) {
		cin >> A.at(i);
	}
	for (int i = 0; i < N; i++) {
		int tmp1 = i - A.at(i), tmp2 = i + A.at(i);
		if (tmp1 >= 0) {
			cnt.at(tmp1).second++;
		}
		if (tmp2 < N) {
			cnt.at(tmp2).first++;
		}
	}

	long long ans = 0;
	for (int i = 0; i < N; i++) {
		long long tmp1 = cnt.at(i).first, tmp2 = cnt.at(i).second;
		ans += tmp1 * tmp2;
	}
	cout << ans << endl;
}

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

int main(){
  string s, t;
  cin >> s;
  cin >> t;
  int x;
  x = s.size();
  t=t.erase(x);

  if(s==t) printf("Yes\n");
  else printf("No\n");

  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAX 200001
const int inf = 1e18;

int mn[2][1010], mx[2][1010];
int a[MAX], dp[2][1010];
signed main(){
	int n, m, k;
	fill((int*)dp, (int*)(dp+2), inf);
	fill((int*)mn, (int*)(mn+2), inf);
	scanf("%lld%lld%lld", &n, &m, &k);
	for(int i = 0;i < n;i++)scanf("%lld", &a[i]);
	
	dp[0][0] = k;
	mn[0][0] = mx[0][0] = a[0];
	for(int i = 1;i < n;i++){
		for(int j = 1;j < m;j++){
			if(dp[0][j-1] == inf)continue;
			mn[1][j] = min(mn[0][j-1], a[i]);
			mx[1][j] = max(mx[0][j-1], a[i]);
			dp[1][j] = dp[0][j-1];
		}
		for(int j = 0;j < m;j++){
			if(dp[0][j] == inf)continue;
			int sum = dp[0][j]+(j+1)*(mx[0][j]-mn[0][j])+k;
			dp[1][0] = min(dp[1][0], sum);
			mx[1][0] = mn[1][0] = a[i];
		}
		for(int j = 0;j < m;j++){
			mn[0][j] = mn[1][j];mn[1][j] = inf;
			mx[0][j] = mx[1][j];mx[1][j] = 0;
			dp[0][j] = dp[1][j];dp[1][j] = inf;
		}
	}
	
	int ans = dp[0][0];
	for(int i = 1;i < m;i++){
		int sum = dp[0][i]+(i+1)*(mx[0][i]-mn[0][i]);
		ans = min(ans, sum);
	}
	printf("%lld\n", ans);
	return 0;
}



Measured memory_bytes: 3432