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

int main() 
{
   string S;
   cin >> S;

   int size = S.size();
   string S2 = S;
   int count1 = 0;
   for (int i = 0; i < size - 1; i++)
   {
      if (S.at(i) == S.at(i+1))
      {
         if (S.at(i+1) == '0')
            S.at(i+1) = '1';
         else
            S.at(i+1) = '0';
         count1++;
      }
   }

   int count2 = 0;
   for (int i = 0; i < size - 1; i++)
   {
      if (S2.at(i) == S2.at(i+1))
      {
         if (i == 0)
         {
            if (S2.at(i) == '0')
               S2.at(i) = '1';
            else
               S2.at(i) = '0';
         }
         else
         {
            if (S2.at(i+1) == '0')
               S2.at(i+1) = '1';
            else
               S2.at(i+1) = '0';
         }
         count2++;
      }
   }
   cout << min(count1, count2) << endl;
}


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

int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  vector<int> L(Q), R(Q);
  for (int i = 0; i < Q; i++) {
    cin >> L.at(i) >> R.at(i);
  }

  //    0 1 2 3 4 5 6 7 8 9
  //sum 0 0 1 1 1 1 1 1 2 2 2 2 2 3
  //S    A C A T C G A C T A G A C
  //i    0 1 2 3 4 5 6 7 8 9
  vector<int> sum(N + 1);
  for (int i = 1; i < N; i++) {
    sum.at(i + 1) = sum.at(i);
    if (S.at(i - 1) == 'A' && S.at(i) == 'C') {
      sum.at(i + 1)++;
    }
  }

  for (int i = 0; i < Q; i++) {
    cout << sum.at(R.at(i)) - sum.at(L.at(i)) << endl;
  }
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  // 文字列
  string str; // 文字列変数を宣言
  int a;
 
  cin >> a;
  cin >> str;
  
  if(a>=3200){
    cout << str << endl;  
  }else{
    cout << "red" << endl; 
  }
  
}

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

bool check(string str){
  for(auto c : str){
    if(!(c=='A' || c =='T' || c=='C' || c=='G')){
      return false;
    }
  }
  return true;
}

int main(void){
  string S;
  cin >> S;

  int length = S.length();
  int max = 0;

  for (int i = 0; i < length; i++){
    for (int j = i; j <length ;j++){
      string str = S.substr(i, length - j);
      if(check(str)==true){
        if(str.length()>max){
          max = str.length();
        }
      }
    }
  }
  cout << max << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n;
    cin >> n;
    int taro = 0,hanako = 0;
    for(int i = 0;i < n;i++)
    {
        string s,t;
        cin >> s >> t;
        if(s == t)
        {
            taro++;
            hanako++;
        }
        else if(s > t)
        {
            taro += 3;
        }
        else
        {
            hanako += 3;
        }
    }
    cout << taro << " " << hanako << "\n";
    
    return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int MOD = 1e9+7;
 
int main() {
	int r;
	cin >> r;
	cout << r*r << endl;
	return 0;
}

Measured memory_bytes: 3624
//coded by: pranonrahman-------------------------------------
//-----------------------------------------------------------
//-----------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
#define O_o ios_base::sync_with_stdio(0)
#define O_O ios_base::sync_with_stdio(0); cin.tie(NULL)
#define o_O ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
#define fixedprecision(n) cout<<fixed<<setprecision(n)
#define endl '\n'
#define CASE(n) cout << "Case " << n << ": "
#define pi acos(-1.0)
#define _____(n) cout << "Dhukse " << n << endl

long long w,h;
char arr[25][25];
long long vis[25][25];
long long xx[]={+1,0,-1,0};
long long yy[]={0,+1,0,-1};
long long check(long long i,long long j)
{
    if(i<0 or i>=h or j<0 or j>=w or arr[i][j]=='#')  return 0;
    return 1;
}

long long bfs(long long i,long long j)
{
    long long mx =0;
    deque<pair<long long,long long>>dq;
    memset(vis,-1,sizeof(vis));
    dq.push_back({i,j});
    vis[i][j]=0;
    while(dq.size())
    {

        long long px = dq.front().first;
        long long py = dq.front().second;
        dq.pop_front();
        for(long long i=0;i<4;i++)
        {
           long long nx=px+xx[i];
           long long ny=py+yy[i];
           if(check(nx,ny)!=0 and vis[nx][ny]==-1 and arr[nx][ny]!='#')
           {
               vis[nx][ny]=vis[px][py]+1;
               mx = max(vis[nx][ny],mx);
               dq.push_back({nx,ny});
           }
        }
    }
   // for(long long i=0;i<h;i++)
   // {
  //      for(long long j=0;j<w;j++)    cout << vis[i][j] << ' ' ;
  //      cout<< endl;
 //   }
  //  cout << endl;
    return mx;
}

int main()
{
    O_o;
    long long t=1;
    //cin >> t;
    long long T=t;
    while(t--)
    {
        cin >> h >> w;
        for(long long i=0;i<h;i++)
        {
            for(long long j=0;j<w;j++)
            {
                cin >> arr[i][j];
            }
        }
        long long mx = 0;
       for(long long i=0;i<h;i++)
        {
            for(long long j=0;j<w;j++)
            {
                if(arr[i][j]!='#')
                {
                    mx = max(mx,bfs(i,j));
                }
            }
        }
        cout << mx << endl;

    }


    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

#define MAX 100000

struct TRAMP{
	char mark;
	int number;
};

TRAMP cards[MAX];

struct ORDER{
	ORDER(){
		number = 0;
		mark_array_index = 0;
	}
	int number;
	int mark_array_index;
	char mark_array[5];
};

ORDER inputedORDER[MAX];
int order_index = 0;

int n;

void registerORDER(char mark,int number){
	int i;
	for(i = 0; i < order_index; i++){
		if(number == inputedORDER[i].number) break;
	}
	if(i == order_index){
		inputedORDER[order_index].number = number;
		inputedORDER[order_index].mark_array[inputedORDER[order_index].mark_array_index++] = mark;
		order_index++;
	}else{
		inputedORDER[i].mark_array[inputedORDER[i].mark_array_index++] = mark;
	}
}

bool compareToORDER(int cards_index){
	int i,k = 0,number = cards[cards_index].number;
	for(i = 0; i < order_index;i++){
		if(number == inputedORDER[i].number) break;
	}
	while(number == cards[cards_index].number && k < inputedORDER[i].mark_array_index){
		if(cards[cards_index].mark != inputedORDER[i].mark_array[k])
			return false;
		else{
			cards_index++;
			k++;
		}
	}
	return true;
}

bool isStable(){
	int history = 0;
	for(int i = 1; i < n; i++){
		if(cards[history].number != cards[i].number || i == n-1){
			if(!compareToORDER(history))
				return false;
			else{
				history = i;
			}
		}
	}
	return true;
}

int Partition(int left,int right){
	int i = left-1,pivot = cards[right].number;
	TRAMP tmp;
	for(int start = left; start < right; start++){
		if(cards[start].number <= pivot){
				i++;
				tmp = cards[i];
				cards[i] = cards[start];
				cards[start] = tmp;
		}
	}

	tmp = cards[right];
	cards[right] = cards[i+1];
	cards[i+1] = tmp;

	return i+1;
}

void quickSort(int left,int right){
	if(left < right){
		int q = Partition(left,right);
		quickSort(left,q-1);
		quickSort(q+1,right);
	}
}


int main(){
	scanf("%d",&n);

	for(int i = 0; i < n; i++){
		scanf("%s %d",&cards[i].mark,&cards[i].number);
		registerORDER(cards[i].mark,cards[i].number);
	}

	quickSort(0,n-1);

	if(isStable()){
		printf("Stable\n");
	}else{
		printf("Not stable\n");
	}

	for(int i = 0; i < n; i++)	printf("%c %d\n",cards[i].mark,cards[i].number);
}

Measured memory_bytes: 3384
#include<stdio.h>
int main(void){
  int a,i,ans;
  ans=4;
  scanf("%d",&a);
  for(i=1;i<=1000000;i++){
    if(a==4 || a==2 || a==1){
      break;
    }
    ans=ans+1;
    if(a%2==0){
      a=a/2;
    }
    else{
      a=3*a+1;
    }
  }
  printf("%d",ans);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>
#include <bitset>
#include <list>
#include <cstdio>
#include <stdio.h>
#include <complex>
#include <math.h>

typedef long long ll;

using namespace std;

double pi=2*acos(0);
const int INF = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};


int main()
{
    int n;
    cin >> n;
    double v[n];
    double tmp;
    for(int i=0; i<n; i++) cin >> v[i];
    sort(v, v+n);
    tmp = v[0];
    for(int i=1; i<n; i++)
    {
        tmp = (tmp + v[i])/2;
    }
    cout << tmp;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(500*500)
N = int(sys.stdin.readline())
edges = [list(map(int,sys.stdin.readline().split())) for _ in range(N - 1)]
A = [[] for _ in range(N + 1)]
 
for edge in edges:
    A[edge[0]].append([edge[1],edge[2]])
    A[edge[1]].append([edge[0],edge[2]])
 
depth = [-1] * (N + 1)
depth[1] = 0
 
def dfs(A,s):
    for v in A[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(A,v[0])    
dfs(A,1)
for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Measured memory_bytes: 102108
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
 
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pair<ll,ll>> vii;
typedef vector<vii> vvii;
typedef pair<ll,ll> ii;
 
#define pb push_back
#define mp make_pair
#define sz(vs) (ll)(vs.size())
#define rep(i,a,b) for (ll i=a;i<b;i++)
#define iter(i,c) for (auto i:c)
#define ss second
#define ff first
#define D(x) cout << '>' << #x << ':' << x << endl;
#define D2(x,a) cout << '>' << #x << ':' << x << " >" << #a << ':' << a <<  endl;
#define D3(x,a,b) cout << '>' << #x << ':' << x << " >" << #a << ':' << a << " >" << #b << ':' << b << endl;
#define D4(x,a,b,c) cout << '>' << #x << ':' << x << " >" << #a << ':' << a << " >" << #b << ':' << b << " >" << #c << ':' << c << endl;
#define PS(a,st,e) if (1) {if (st<e) {cout<<a[st];rep(noname,st+1,e) cout<<""<<a[noname];}cout<<"\n";}
#define PA1(a,st,e) if (1) {if (st<e) {cout<<a[st];rep(noname,st+1,e) cout<<" "<<a[noname];}cout<<'\n';}
#define PA(a,st,e) if (1) {cout<<#a<<": [";if (st<e) {cout<<a[st];rep(noname,st+1,e) cout<<", "<<a[noname];}cout<<"]\n";}
#define PSET(c) if (1) {cout<<#c<<": {";for (auto noname:c) cout<<noname<<",";cout<<"}\n";}
#define PM(c) if (1) {cout<<#c<<": {";for (auto noname:c) cout<<noname.first<<":"<<noname.second<<", ";cout<<"}\n";}


#define MAXN 7
#define mod 1000000007

ll n, m, k, r[MAXN], c[MAXN];
string s;
vi rowsofcol[MAXN];
char ch;

ll subsetsum(ll k_, ll n_) {
	if (k_<0) return 0;
	if (n_==0 && k_!=0) return 0;
	if (n_==0) return 1;
	return (subsetsum(k_,n_-1) + subsetsum(k_-r[n_], n_-1));
}

void countans(ll i, vi selectedcols, ll &ans) {
	if (i==m+1) {
		ans += subsetsum(k, n);
		return;
	}
	//ith column is not selected
	countans(i+1, selectedcols, ans);
	//ith column is selected
	k -= c[i];
	rep(j, 0, sz(rowsofcol[i])) --r[rowsofcol[i][j]];
	selectedcols.pb(i);
	countans(i+1, selectedcols, ans);
	k += c[i];
	rep(j, 0, sz(rowsofcol[i])) ++r[rowsofcol[i][j]];
	selectedcols.pop_back();
}

void solve() {
	cin>>n>>m>>k;
	memset(r,0,sizeof(r));
	memset(c,0,sizeof(c));
	ll countblack = 0;
	rep(i,1,n+1) {
		rep(j,1,1+m) {
			cin>>ch;
			if (ch=='#') {r[i]++;c[j]++;rowsofcol[j].pb(i);countblack++;}
		}
	}
	k = countblack - k;
	vi col;
	ll ans = 0;
	countans(1, col, ans);
	cout<<ans<<endl;
}
 
void aux() {
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	aux();
	ll _ = 1;
	// cin>>_;
	while(_--) {
		solve();
	}
	return 0;
}

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

using namespace std;

const int N = 1e5 + 10;

int n, m;
int cnt[N], vis[N];

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    cnt[i] = 1;
  }
  vis[1] = 1;
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    if (vis[x]) {
      vis[y] = 1;
    }
    ++cnt[y];
    if ((--cnt[x]) == 0) {
      vis[x] = 0;
    }
  }
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (vis[i]) ++cnt;
  }
  cout << cnt;
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000000
#define MOD 1000000007
#define MAXR 100000
#define _GLIBCXX_DEBUG

int threemax(int a, int b, int c) {
	if (a >= b && a >= c) {
		return a;
	}
	else if (b >= a && b >= c) {
		return b;
	}
	else {
		return c;
	}
}

int threemin(int a, int b, int c) {
	if (a <= b && a <= c) {
		return a;
	}
	else if (b <= a && b <= c) {
		return b;
	}
	else {
		return c;
	}
}

void chmaxl(ll &a,ll b){
	if(a<b){
		a=b;
	}
	return;
}

void chminl(ll &a,ll b){
	if(a>b){
		a=b;
	}
	return;
}

void chmaxi(int &a,int b){
	if(a<b){
		a=b;
	}
	return;
}

void chmini(int &a,int b){
	if(a>b){
		a = b;
	}
	return;
}



int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  for(int i = 0; i < n; i++){
    cin >> p[i];
  }
  int ans = 0;
  for(int i = 1; i < n - 1; i++) {
    if((p[i - 1] < p[i]) && (p[i] < p[i + 1])){
      ans++;
    }
    else if((p[i - 1] > p[i]) && (p[i] > p[i + 1])){
      ans++;
    }
  }
  cout << ans;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        try (
            Scanner sc = new Scanner(System.in);
        ) {
            String[] hw = sc.nextLine().split("\\s");
            int h = Integer.parseInt(hw[0]);
            int w = Integer.parseInt(hw[1]);
            List<String> lineList = new ArrayList<>();
            for (int i = 0; i < h; i++) {
                lineList.add(sc.nextLine());
            }
            
            for (int i = 0; i < w + 2; i++) {
                System.out.print('#');
            }
            System.out.println();
            
            for (String line : lineList) {
                System.out.print('#');
                System.out.print(line);
                System.out.println('#');
            }
            
            for (int i = 0; i < w + 2; i++) {
                System.out.print('#');
            }
            System.out.println();
        }
    }

}


Measured memory_bytes: 24660
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;

long long MOD = 1000000007;

int main(){
    int a;
    string s;

    cin >> a >> s;
    if(a>=3200){
        cout << s << endl;
    }else{
        cout << "red" << endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int n, A[50];

int solve(int i, int m)
{
	if (m == 0) return 1;
	if (i >= n) return 0;
	int res = solve(i + 1, m) || solve(i + 1, m - A[i]);
	return res;
}

int main()
{
	int q, M, i;

	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &A[i]);
	scanf("%d", &q);
	for (i = 0; i < q; i++)
	{
		scanf("%d", &M);
		if (solve(0, M)) printf("yes\n");
		else printf("no\n");
	}

	return 0;
}


Measured memory_bytes: 2516
/*input
2 4
2 3
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define pb push_back
#define f first
#define s second
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,K;
int a[1001];
int dp[100010][2];
int solve(int k,int turn){
	// cout << k <<" "<< turn << endl;
	if(dp[k][turn]!=-1){
		return dp[k][turn];
	}
	if(turn == 0){
		bool flag = 0 ;
		// if flag = 1 I win , else I lose
		for(int i=0;i<n;i++){
			if(a[i]<=k){
				flag|=solve(k-a[i],!turn);
			}
		}
		// returns 0 if I cant win , 1 if I win 
		return dp[k][turn] = flag ; 
	}
	else {
		//turn = 1 means second players moves
		bool flag = 1 ;
		// I ll get in return 0 if 0 loses 
		for(int i =0 ; i < n ; i++){
			if(a[i]<=k){
				flag &= solve(k-a[i],!turn);
			}
		}
		// flag = 0 if I win , else 1
		return dp[k][turn] = flag ;
	}

}
signed main() {
	IOS;
	cin>>n>>K;
	memset(dp,-1,sizeof(dp)); 
	for(int i=0;i<n;i++)cin>>a[i];
	int ans = solve(K,0);
	if(ans == 1 ){
		cout << "First\n";
	}
	else
		cout << "Second\n";

return 0;
}


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

int main() {
  int N, M;
  scanf("%d %d", &N, &M);

  vector<int> v(N + 1, 0);
  for(int i = 0; i < M; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    v[a]++;
    v[b]++;
  }
  
  for(int i = 1; i < N+1; i++){
    printf("%d\n", v[i]);
  }
}


Measured memory_bytes: 256
N, W = list(map(int, input().split()))

w = []
v = []
for _ in range(N):
    wv = list(map(int, input().split()))
    w.append(wv[0])
    v.append(wv[1])

dp = [[0, 0]]
for i in range(1, W+1):
    max_t = dp[i-1][0]
    flag = dp[i-1][1]
    for j in range(N):
        if w[j] > i or dp[i-w[j]][1] & (1 << j):
            continue
        if max_t < dp[i-w[j]][0] + v[j]:
            max_t = dp[i-w[j]][0] + v[j]
            flag = dp[i-w[j]][1] | (1 << j)
    dp += [[max_t, flag]]
print(dp[W][0])


Measured memory_bytes: 58204
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vi>;

const long long int llinf = 1LL << 62;
const int inf = 99999999;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };

#define Endl endl
#define pr(x) cout << x << endl
#define FOR(i,a,b) for(int i = a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb(a) push_back(a);
#define mp(a,b) make_pair(a,b)
#define atcoder int(1e9) +7;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
#define all(x) x.begin,x.end();

int main() {
	
	ll a, b, c;
	cin >> a >> b >> c;
	ll cnt = 0;

	while (1) {
		if (a % 2 == 1 || b % 2 == 1 || c % 2 == 1)
			break;
		if (a == b && b == c) {
			cnt = -1;
			break;
		}

		ll copya = a, copyb = b, copyc = c;
		a = copyb / 2 + copyc / 2;
		b = copya / 2 + copyc / 2;
		c = copya / 2 + copyb / 2;
		cnt++;
	}
	

	pr(cnt);

	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize "O3"

#define F first
#define S second
#define ALL(x) x.begin(), x.end()

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = 0;

int main() {
  int n, a, b; scanf("%d %d %d", &n, &a, &b);
  puts((abs(a - b) & 1) ? "Borys" : "Alice");
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void) {
	int N, i, A;
	double S = 0.0;
	scanf("%d",&N);
	for (i = 0; i < N; i++) {
		scanf("%d",&A);
		S += 1.0 / A;
	}
	printf("%f",1/S);

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
/* #define int long long */
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define repa(i, s, n) for(int i = s; i < (int)n; i++)
using namespace std;
using ll = long long;
typedef vector<int> vi;
typedef pair<int, int> P;
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};

signed main(){
    int h, w;
    cin >> h >> w;
    vector<string>s(h);
    int si, sj;
    cin >> si >> sj;
    int ti, tj;
    cin >> ti >> tj;
    --si; --sj; --ti; --tj;

    rep(i, h) cin >> s[i];

    const int INF = 1e9;

    vector<vector<int>> dist(h, vector<int>(w, INF));
    deque<P> q; /* 座標を入れる */
    dist[si][sj] = 0;

    q.emplace_back(si, sj);

    while(!q.empty()){
        int i = q.front().first;
        int j = q.front().second;
        q.pop_front();
        int d = dist[i][j];
        rep(v, 4){
            int ni = i+di[v], nj = j+dj[v];
            if(ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
            if(s[ni][nj] == '#') continue;
            if(dist[ni][nj] <= d) continue;
            dist[ni][nj] = d;
            q.emplace_front(ni, nj);
        }
        for(int ei = -2; ei <= 2; ++ei){
            for(int ej = -2; ej <= 2; ++ej){
                int ni = i+ei, nj = j+ej;
                if(ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
                if(s[ni][nj] == '#') continue;
                if(dist[ni][nj] <= d) continue;
                dist[ni][nj] = d+1;
                q.emplace_back(ni, nj);
            }
        }
    }

    int ans = dist[ti][tj];
    if(ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}

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

const int N = 1e2 + 5;
const int W = 1e5 + 5;

int peso [N], lucro [N];
long long dp [N][W];

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, w;
  cin >> n >> w;
  for (int i = 1; i <= n; i++) {
    cin >> peso[i] >> lucro[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= w; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j - peso[i] >= 0) {
        dp[i][j] = max (dp[i][j], dp[i - 1][j - peso[i]] + lucro[i]);
      }
    }
  }
  cout << dp[n][w] << '\n';
  return 0;
}

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

using namespace std;

int main() {

    string t;
    cin >> t;

    map <char, int> a;
    int ans = 1e9;

    for (int i = 0; i < t.size(); ++i) {
        a[ t[i] ]++;
    }


    for (auto it = a.begin(); it != a.end(); ++it) {

       char c = (*it).first;

        bool flag = true;

        if (count (t.begin(), t.end(), c) == t.size()) flag = false;


        int cur = 0;
        string t1 = t;
        while (flag) {

            string s;

            for (int i = 0; i < t1.size() - 1; ++i) {
                if (t1[i] == c || t1[i + 1] == c) {
                    s.push_back(c);
                } else s.push_back(t1[i]);
            }

            cur++;
            if (count (s.begin(), s.end(), c) == s.size()) flag = false; else t1 = s;

        }

        ans = min (cur, ans);

    }

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.IO.Pipes;
using System.Linq;
using System.Numerics;

namespace Atcoder
{
	class Program
	{
		/*
			string s = Console.ReadLine();
			string[] ST = Console.ReadLine().Split(' ').ToArray();
			string S = strArray[0];
			string T = strArray[1];

			int[] HWN = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
			int H = intArray[0];
			int W = intArray[1];
			int N = int.Parse(Console.ReadLine());

			List<int> A = new List<int>(Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToList());
			
			double[] R = Console.ReadLine().Split(' ').Select(i => double.Parse(i)).ToArray();

			Boolean ok = false;
			
			List<int> dp = Enumerable.Repeat(値, 個数).ToList();
			
			Console.WriteLine(ans);
			Console.WriteLine("Yes");
			Console.WriteLine("No");
			Console.ReadKey();
			Console.WriteLine(cnt);

			for(int i= 0; i < N; i++)
			(char)((a + N - 'a') % 26 + 'a') + "";
		*/

		static void Main(string[] args)
		{
			long N = long.Parse(Console.ReadLine());
			string ans = "";
			long by = N;
			long dot = 0;
			char a = (char)('a');
			string z = "z";


            while (by != 0)
            {
				by--;
				dot = by % 26;

				//if (dot == 0)
				//	ans = z + ans;
				//else
					ans = (char)(a + dot) + "" + ans;
				by /= 26;
			}
			Console.WriteLine(ans);
		}

		class Item : IComparable
		{
			public string A;
			public int B;
			public Item(string a, int b)
			{
				this.A = a;
				this.B = b;
			}
			public int CompareTo(object obj)
			{
				return B - ((Item)obj).B;
			}
		}

		/// <summary>
		/// 回文
		/// </summary>
		/// <param name="Target"></param>
		/// <param name="len"></param>
		/// <returns></returns>
		static bool Palindrome(string Target , int len)
        {
			bool yes = true;

			for(int i = 0;i < len; i++)
            {
				if(Target[i] != Target[len - 1 - i])
                {
					yes = false;
					break;
                }
            }
			return yes;
        }

		/// <summary>
		/// アナグラム
		/// </summary>
		/// <param name="word1"></param>
		/// <param name="word2"></param>
		/// <returns></returns>
		static bool IsAnagramOf(string word1, string word2)
		{
			//char[] val1 = word1.ToCharArray();
			//char[] val2 = word2.ToCharArray();
			//Array.Sort(val1);
			//Array.Sort(val2);
			//word1 = new string(val1);
			//word2 = new string(val2);

			//return word1 == word2;
			return word1.OrderBy(x => x).SequenceEqual(word2.OrderBy(x => x));
		}

		/// <summary>
		/// 最小公倍数
		/// </summary>
		/// <param name="a"></param>
		/// <param name="b"></param>
		/// <returns></returns>
		public static BigInteger Lcm(BigInteger a, BigInteger b)
		{
			return a * b / Gcd(a, b);
		}

		/// <summary>
		/// 最大公約数
		/// </summary>
		/// <param name="a"></param>
		/// <param name="b"></param>
		/// <returns></returns>
		public static BigInteger Gcd(BigInteger a, BigInteger b)
		{
			if (a < b)
				// 引数を入替えて自分を呼び出す
				return Gcd(b, a);
			while (b != 0)
			{
				var remainder = a % b;
				a = b;
				b = remainder;
			}
			return a;
		}
	}
}

Measured memory_bytes: 27392
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
import collections
from heapq import *
#RRR...WWW...にしたい
N=int(input())
stones=list(input())
#print(stones)
l=0
r=N-1
wchange=0
rchange=0
cnt=0
while l<r:
    if (wchange==0)and(stones[l]=="W"):
        wchange=1
    elif (wchange==0)and(stones[l]=="R"):
        l=l+1

    if (rchange==0)and(stones[r]=="R"):
        rchange=1
    elif (rchange==0)and(stones[l]=="W"):
        r=r-1

    if wchange+rchange==2:
        buf=stones[l]
        stones[l]=stones[r]
        stones[r]=buf
        cnt=cnt+1
        wchange=0
        rchange=0
    #print(l,wchange,r,rchange,stones)
print(cnt)




Measured memory_bytes: 82764
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n = ni()
a = [ni() for _ in range(n)]
b = [ai for ai in a]

first = max(a)
a.remove(first)
second = max(a)

for bi in b:
    print(first if bi != first else second)

Measured memory_bytes: 14068
#include<stdio.h>

int  main(){

  int a=0;

  int W,H,x,y,r=0;

  scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);

  if(x-r>=0&&x+r<=W){

    if(y-r>=0&&y+r<=H){

      a=1;

    }

  }

  else{

    a=0;

  }

  if(a==1){

    printf("Yes\n");

  }

  else if(a==0){

    printf("No\n");

   }

  return 0;

}
 

Measured memory_bytes: 584
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
#include <map>
#include <set>

using namespace std;

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

const ll mod = 1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;   // INFの値は1152921504606846976

ll dp[100005];

int main()
{
    int n,m;
    cin >> n >> m;
    int a[m];
    dp[0] = 1;
    bool z = false;
    for(int i = 0; i < m; i++){
        cin >> a[i];
        dp[a[i]] = -1;
    }
    for(int i = 1; i < m; i++){
        if(a[i] - a[i-1] == 1) z = true;
    }
    if(a[0] != 1){
        dp[1] = 1;
    }else{
        dp[1] = 0;
    }
    
    for(int i = 0; i <= n; i++){
        if(dp[i+2] != -1){
            if(dp[i] == -1){
                dp[i+2] = dp[i+1];
            }else if(dp[i+1] == -1){
                dp[i+2] = dp[i];
            }else{
                dp[i+2] = dp[i+1] + dp[i];
                dp[i+2] %= mod; 
            }
        }
    }
    if(z){
        cout << 0 << endl;
    }else{
        cout << dp[n];
    }


}   

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define Mod 1000000007
int main()
{
    ll n,k;
    cin>>n>>k;
    vector<ll> v(n),dp(n);
    for(ll i=0;i<n;i++) cin>>v[i];
    for(ll i=1;i<n;i++)
    {
        ll val=999999999999;
        for(ll j=1;j<=k;j++)
            if(i>=j)
                val=min(dp[i-j]+abs(v[i]-v[i-j]),val);
        dp[i]=val;
    }
    cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 4848
#include<bits/stdc++.h>
using namespace std;
#include <math.h>
#define ll long long 
// to increase precision
// std::cout<<std::fixed;
// 	std::cout<<std::setprecision(6)<<z;
#define max1 100001

//long long int mod=1e18 ;
vector<vector<int> > adjl(max1);
int vis[max1];
double pi=3.1415926535;
void dfs(int a){
	vis[a]=1;
	for(int i=0;i<adjl[a].size();i++){
		int ch=adjl[a][i];
		if(!vis[ch]){
			dfs(ch);
		}
	}
}


int main(){	
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		adjl[a].push_back(b);
		adjl[b].push_back(a);
	}
	int flag=1;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			if(i!=1){
				flag=0;
				break;
			}
			dfs(i);
		}
	}

	if(flag){
		memset(vis,0,sizeof(vis));
		queue<int> q;
		q.push(1);
		vector<int> ans(n+1);
		vis[1]=1;
		while(!q.empty()){
			int ind=q.front();
			q.pop();
			
			for(int i=0;i<adjl[ind].size();i++){
				int ch=adjl[ind][i];
				if(!vis[ch]){
					vis[ch]=1;
					q.push(ch);
					ans[ch]=ind;
				}
			}
			
		}
		cout<<"Yes"<<endl;
			for (int i = 2; i <=n; ++i)
			{
				cout<<ans[i]<<endl;
			}
	}
	else{
		cout<<"No"<<endl;
	}


		
}
	
	
	
	





Measured memory_bytes: 14008
#include <bits/stdc++.h>
#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 equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const long double EPS = 1e-10;

class Point {
  public:
  long double x, y;

  Point(long double x = 0, long double y = 0): x(x), y(y) {}

  Point operator + (Point &p) {
    return Point(x + p.x, y + p.y);
  }

  Point operator - (Point &p) {
    return Point(x - p.x, y - p.y);
  }

  Point operator * (long double k) {
    return Point(x * k, y * k);
  }

  Point operator / (long double k) {
    return Point(x / k, y / k);
  }

  bool operator < (const Point &p) const {
    return x != p.x ? x < p.x : y < p.y;
  }

  bool operator == (const Point &p) const {
    return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
  }
};

int main() {
  Point p1, p2;
  cin >> p1.x >> p1.y >> p2.x >> p2.y;

  Point v = p2 - p1, res = p2;
  rep(i, 2) {
    v.y *= -1;
    swap(v.x, v.y);
    res = res + v;
    if (i) cout << " ";
    cout << res.x << " " << res.y;
  }
  cout << endl;



  
  return 0;
}

Measured memory_bytes: 256
N = int(input())

d = [[0]*9 for _ in range(9)]

for i in range(1, N + 1):
    if i % 10 == 0:
        continue
    s = str(i)
    x = int(s[-1])
    y = int(s[0])
    d[x-1][y-1] += 1

ans = 0
for i in range(9):
    for j in range(9):
        ans += d[i][j] * d[j][i]
print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0)
#define so sizeof
#define pb push_back
#define vl vector<ll>
#define el endl;cout.flush()
#define be begin()
#define fi first
#define se second
#define br break
#define sz size()
#define en end()
#define ro return 0
#define br break
#define con continue
#define um unordered_map<ll,ll>
#define ms(x) memset(x , 0, so x)
#define all(x) (x).be , (x).en
#define rall(x) (x).rbegin() , (x).rend()
#define acc(x) accumulate((x).be , (x).en , 0ll)
#define forn(i,a,b) for(ll i=a;i<=b;++i)
#define forr(i,a,b) for(ll i=a;i<b;++i)
#define rng_58 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define plll pair<ll,pair<ll,ll>>
#define plvl pair<pair<ll,ll> ,ll>
#define mp make_pair
#define trace2(a,b) cerr <<"a is " << a << " b is " << b << el;
#define trace3(a,b,c) cerr <<"a is " << a << " b is " << b << " c is " << c << el;
#define trace4(a,b,c,d) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << el ;
#define trace5(a,b,c,d,e) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << el;
#define trace6(a,b,c,d,e,f) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << " f is " << f << el ;
int main()
{
    ios;
    ll a , b ;
    cin >> a >> b ;
    if(a <= b) swap(a , b);
    ll ans = 0 ;
    ans = ans + a ;
    a-- ;
    if(a <=b) swap(a , b ) ;
    ans = ans + a ;
    cout << ans << el ;
    ro ;
}

































Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

// 素因数分解O(√n)
// 12 -> [(2,2), (3,1)] (2^2*3^1)

vector<pair<ll,int>> factorize(ll n) {
  vector<pair<ll,int>> res;
  for (ll i = 2; i*i <= n; ++i) {
    if (n%i) continue;
    res.emplace_back(i,0);
    while (n%i == 0) {
      n /= i;
      res.back().second++;
    }
  }
  if (n != 1) res.emplace_back(n,1);
  return res;
}

int n;
map<ll, int> f; // n! = p1^f1*p2^f2*...pk ^fk

//rec(p,mul): fのイテレータp以降について約数の個数をmulにするような場合の数
ll rec(map<ll,int>::iterator p, ll mul) {
  if (p == f.end()) {
    if (mul == 1) return 1;
    else return 0;
  }
  ll res = 0;
  rep(i,p->se+1) {
    // pを何個使うか(区間[0,f]の間で)
    if (mul%(i+1) != 0) continue;
    res += rec(++p, mul/(i+1));
    --p;
  }
  return res;
}

int main () {
  cin >> n;
  for (int i = 2; i <= n; ++i) {
    auto ps = factorize(i);
    for (auto it : ps) f[it.fi] += it.se;
  }
  //for (auto p : f)  printf("%d %d\n", p.fi, p.se);
  cout << rec(f.begin(), 75) << endl;
  return 0;
}

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

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

const int maxn = 200010;

int prf[maxn];

int main() {
    int N, K;
    cin >> N >> K;
    V<int> A(N);
    rep(i, N) cin >> A[i];

    rep(t, K) {
        memset(prf, 0, sizeof(prf));
        rep(i, N) {
            prf[max(0, i - A[i])]++;
            prf[min(N, i + A[i] + 1)]--;
        }
        bool ch = 0;
        rep(i, N) {
            prf[i + 1] += prf[i];
            if (prf[i] != A[i]) {
                ch = 1;
            }
            A[i] = prf[i];
        }
        if (!ch) break;
    }

    rep(i, N) { printf("%d%c", A[i], i == N - 1 ? '\n' : ' '); }

    return 0;
}

Measured memory_bytes: 4824
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; 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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

    ll n, m;
    cin >> n >> m;
    vector<P> a, b;
    ll p, y;
    REP(i, m){
        cin >> p >> y;
        a.push_back(P{y, p});
        b.push_back(P{y, p});
    }
    VSORT(a);
    vll cnt(n + 1, 0);
    map<P, ll> mp;
    REP(i, m){
        ll as = a[i].second;
        cnt[as]++;
        mp[a[i]] = cnt[as];
    }
    REP(i, m){
        ll bs = b[i].second, num = mp[b[i]], d1 = 0, d2 = 0, tmp;
        tmp = bs;
        while(tmp){
            d1++;
            tmp /= 10;
        }
        tmp = num;
        while(tmp){
            d2++;
            tmp /= 10;
        }
        REP(i, 6 - d1) cout << "0";
        cout << bs;
        REP(i, 6 - d2) cout << "0";
        cout << num << endl;
    }
    return 0;
}


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

int main() {
				    // *constraint*
  int A,B;    	    // 10000<=A<=B<=99999 
  				    // Enter an Integer
  cin  >> A >> B;
  int count = 0;
  int a,b,c,d,e;
  int tmp;
  int i = A;
  while (i <= B) {
    tmp = i;
    a = tmp % 10;
    b = (tmp /= 10) % 10;
    c = (tmp /= 10) % 10;
    d = (tmp /= 10) % 10;
    e = (tmp /= 10) % 10;
    
    if(a == e && b == d){
      count++;
    }
    i++;
  }
  cout << count << endl;
}


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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

// clang-format off
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) { return stream << p.first << "," << p.second; }
template <typename T>
void print(const vector<T> vec) { rep (i, vec.size() - 1) cout << vec[i] << ' '; cout << vec[vec.size() - 1] << '\n'; }
template <typename Arg>
void print(const Arg arg) { cout << arg << '\n'; }
template <typename Head, typename... Args>
void print(const Head head, const Args... args) { cout << head << " "; print(args...); }
template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) { rep (i, v.size()) cin >> v[i] >> w[i]; }
template <typename T>
void init(vector<T>& v) { rep (i, v.size()) cin >> v[i]; }
template <typename T>
T sum_(vector<T> vec, T init = 0) { return std::accumulate(all(vec), T(init)); }
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m=0) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    int ans = n * (n - 1) / 2 + m * (m - 1) / 2;
    print(ans);

    return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF (1LL<<25)     //33554432
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

signed main(void)
{
  int n;
  string s;
  cin >> s >> n;

  REP(i, s.size()) {
    if(s[i] != 'a' && 'z' - s[i] + 1 <= n) {
      n -= 'z' - s[i] + 1;
      s[i] = 'a';
    }
    //cout << n << endl;
  }

  if(n > 0) s[s.size()-1] += n%26;

  cout << s << endl;
  return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define pb push_back
#define nl cout<<"\n"
#define F first
#define S second
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD )
{
    x += y;
    if( x >= m )
        x -= m;
}

template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD )
{
    x -= y;
    if( x < 0 )
        x += m;
}

int main() 
{
    fastio();

    int k,a,b;
    cin>>k>>a>>b;

    int count = b/k - (a-1)/k;

    if( count > 0 )
        cout<<"OK";
    else
        cout<<"NG";

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

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

ll add(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a+b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll mul(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a*b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

const int N = 100000+5;

int S;
int frec[N];
vi divisors;

ll f(int x){
	return 1LL * x * (x + 1) / 2LL;
}

bool find(int x, int limit){
	ll prefix = 1LL * limit * (limit + 1) / 2LL;
	int lo = 0, hi = limit - 1;
	while(lo < hi){
		int mi = lo + (hi - lo + 1) / 2;
		if(prefix - f(mi) < x) hi = mi-1;
		else lo = mi;
	}
	return prefix - f(lo) == x;
}

int main(){
	ri(S);
	for(int i=1; i * i <= S; i++){
		if(S % i == 0){
			divisors.emplace_back(i);
			if(i * i != S) divisors.emplace_back(S / i);
		}
	}
	for(int i=1; i <= S; i++){
		for(int d : divisors){
			frec[d] += find(d, i);
		}
	}
	ll ans = 0LL;
	for(int d : divisors){
		ans += 1LL * frec[d] * frec[S / d];
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 3332
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    d = defaultdict(int)
    for a in A:
        d[a] += 1
    for _ in range(M):
        B, C = map(int, input().split())
        d[C] += B

    sort_d = sorted(d.items(),reverse = True)

    cnt = 0
    ans = 0
    for i,j in sort_d:
        if cnt + j < N:
            ans += i * j
            cnt += j
        elif cnt + j >= N:
            if cnt == N:
                break
            ans += i * (N - cnt)
            break 

    print(ans)



main()

Measured memory_bytes: 93464
#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return x

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return x

def int_map():
    return map(int,input().split())

def int_list():
    return list(map(int,input().split()))

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import numpy as np
import statistics
import math
import collections

# main code
H,W,M = int_map()
hw = int_mtx(M)

h = []
w = []
for hhww in hw:
    h.append(hhww[0])
    w.append(hhww[1])

ch = collections.Counter(h)
cw = collections.Counter(w)
a = ch.most_common()[0][1]
b = cw.most_common()[0][1]

if a == M or b == M:
    print(M)
    exit()

if a < b:
    bb = cw.most_common()[0][0]
    hw1 = [i for i in hw if not i[1] == bb]
    
    h1 = []
    for hhww in hw1:
        h1.append(hhww[0])

    ch1 = collections.Counter(h1)
    a1 = ch1.most_common()[0][1]

    print(b+a1)
    exit()
else:
    aa = ch.most_common()[0][0]
    hw1 = [i for i in hw if not i[0] == aa]
    
    w1 = []
    for hhww in hw1:
        w1.append(hhww[1])

    cw1 = collections.Counter(w1)
    b1 = cw1.most_common()[0][1]

    print(a+b1)
    exit()



Measured memory_bytes: 151392