akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>
#include <string.h>
#include <bitset>

using namespace std;
typedef long long ll;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

const int inf = 1LL << 55;

#define MAX_N 1002020

typedef long long int64;

// 参考
// https://emtubasa.hateblo.jp/entry/2018/10/31/000000_1

const int64 mod = 1e9 + 7;

inline int64 extgcd(int64 a, int64 b, int64 &x, int64 &y)
{
  int64 d = a;
  if(b != 0) d = extgcd(b, a % b, y, x), y -= (a / b) * x;
  else x = 1, y = 0;
  return d;
}

inline int64 modPow(int64 x, int64 n)
{
  if(n == 0) return 1;
  int64 ret = modPow(x, n/2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return ret;
}

inline int64 modInv(int64 a)
{
  return modPow(a, mod - 2);
}

inline int64 modFact(int n)
{
  int64 ret = 1;
  while(n > 1) (ret *= n--) %= mod;
  return ret;
}

inline int64 modComb(int64 n, int64 r)
{
  static int64 fact[MAX_N], invfact[MAX_N];
  if(fact[0] == 0) {
    fact[0] = invfact[0] = 1;
    for(int i = 1; i < MAX_N; i++) {
      fact[i] = fact[i-1] * i % mod;
      invfact[i] = modInv(fact[i]);
    }
  }
  if(r < 0 || n < r) return 0;
  return fact[n] * invfact[r] % mod * invfact[n-r] % mod;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);
  
  int h, w, a, b;
  cin >> h >> w >> a >> b;
  int ans = 0;
  reps(i, b, w) {
    int x = modComb(i+h-a-1, i) % mod;
    int y = modComb(w-i-1+a-1, a-1) % mod;
    (ans += (x*y)%mod) %= mod;
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 15872
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=2e5+5;
const int mod=1e9+7;

int n,k,a[N];
signed main(){
    FastIO;
    cin>>n>>k;
    rep(i,1,n) cin>>a[i];
    rep(i,1,k){
        int sum[N]{0};
        bool ok=1;
        rep(j,1,n){
            int l=max(1,j-a[j]);
            int r=min(n,j+a[j]);
            sum[l]++;
            sum[r+1]--;
        }
        rep(j,1,n){
            sum[j]+=sum[j-1];
            a[j]=sum[j];
            if(a[j]!=n) ok=0;
        }
        if(ok) break;
    }
    rep(i,1,n) cout<<a[i]<<' ';
    return 0;
}


Measured memory_bytes: 5220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+100;
const int MOD = 1e9+7;
vector<int> p[N];
int n; ll ans=1;
ll work(int a,int b){
    ll rs=1;
    for(int i=0,j=0,c=0;i<p[b].size();++i){
        while(j<p[a].size()&&p[a][j]<p[b][i]) j++,c++;
        rs*=c; c--;
    }
    return rs;
}
int main(){
    scanf("%d",&n); int c=0;
    for(int i=1,j;i<=n;++i){
        scanf("%d",&j); if(j==0) c++;
        p[j].push_back(i);
    }
    if(c>3) ans=0;
    else if(c>=2) ans=6;
    else if(c==1) ans=3;
    else ans=0;
    for(int i=1;i<=n;++i)
        ans=ans*work(i-1,i)%MOD;
    printf("%lld\n",ans);
}

Measured memory_bytes: 5760
#include <iostream>

using namespace std;

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

    int all = 0;
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        all += r - l + 1;
    }
    cout << all << '\n';
}


Measured memory_bytes: 256
#include <iostream>
#include <string.h>
using namespace std;
int dp[100005];
int a[101];
int has[101];
int main() {
	int N; cin >> N;
	int K; cin >> K;
	for (int i = 1; i <= N; i++) cin >> a[i];
	dp[0] = 0;
	for (int i = 1; i <= K; i++) {
		memset(has, 0, sizeof(has));
		for (int j = 1; j <= N; j++) {
			if (i >= a[j]) {
				has[dp[i-a[j]]] = true;
			}
		}
		for (int j = 0; j <= 100; j++) {
			if (not has[j]) {
				dp[i] = j;
				break;
			}
		}
	}
	if (dp[K]) cout << "First" << endl;
	else cout << "Second" << endl;
}


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

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		for (;;) {
			int h = in.nextInt();
			int w = in.nextInt();
			if ((h | w) == 0)
				break;
			int val[][] = new int[150][150];
			int input = h * h + w * w;
			for (int i = 1; i <= 150; i++) {
				for (int j = 1; j <= 150; j++) {
					val[i - 1][j - 1] = i * i + j * j;
				}
			}
			int ansH = 101;
			int ansW = 101;
			boolean judge = false;
			for (int i = input; i <= 150 * 150; i++) {

				for (int j = 1; j <= 150; j++) {
					for (int k = 1; k <= 150; k++) {
						if (j >= k || (j == h && k == w)) {
							continue;
						}
						if (i == val[j - 1][k - 1]) {
							if(h < j || i>input){
								if (j < ansH) {
									ansH = j;
									ansW = k;
									judge = true;
								}
							}
						}
					}
				}
				if (judge) {
					break;
				}
			}
			System.out.println(ansH + " " + ansW);
		}
	}

	static public void debug(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}
}

Measured memory_bytes: 32768
S = input()
flag = True
if S[0] != "A":
    flag = False
s_n = S[2:-1]
c_c = 0
ci = 0
for i,si in enumerate(s_n):
    if si == "C":
        ci = i+2
        c_c += 1

if c_c != 1:
    flag = False

for i,si in enumerate(S):
    if i == 0 or i == ci:
        continue
    if not si.islower():
        flag = False

print("AC") if flag else print("WA")


Measured memory_bytes: 3064
n = int(input())
if n == 2:
  print(-1)
if n == 3:
  print("aa.")
  print("..b")
  print("..b")
if n == 4:
  ans = ["aabc","ddbc","bcaa","bcdd"]
  print(*ans,sep="\n")
if n == 5:
  ans = ["aabbc","dde.c","..eab","a..ab","accdd"]
  print(*ans,sep="\n")
if n == 6:
  ans = ["aa.bbc","..de.c","..deff","aabcc.","d.b..a","dcc..a"]
  print(*ans,sep="\n")
if n == 7:
  ans = ["aab.cc.","..bd..e","ff.d..e","..g.hhi","..gj..i","kllj...","k..mmnn"]
  print(*ans,sep="\n")
if n >= 8:
  ans = [["." for i in range(n)] for j in range(n)]
  ch = [list("aabc"),list("ddbc"),list("bcaa"),list("bcdd")]
  x = n//4-1
  y = n%4+4
  for i in range(x):
    for j in range(4):
      for k in range(4):
        ans[i*4+j][i*4+k] = ch[j][k]
  if y == 4:
    for j in range(4):
      for k in range(4):
        ans[x*4+j][x*4+k] = ch[j][k]
  elif y == 5:
    ch2 = ["aabbc","dde.c","..eab","a..ab","accdd"]
    for j in range(5):
      for k in range(5):
        ans[x*4+j][x*4+k] = ch2[j][k]
  elif y == 6:
    ch2 = ["aa.bbc","..de.c","..deff","aabcc.","d.b..a","dcc..a"]
    for j in range(6):
      for k in range(6):
        ans[x*4+j][x*4+k] = ch2[j][k]
  elif y == 7:
    ch2 = ["aab.cc.","..bd..e","ff.d..e","..g.hhi","..gj..i","kllj...","k..mmnn"]
    for j in range(7):
      for k in range(7):
        ans[x*4+j][x*4+k] = ch2[j][k]

  for row in ans:
    print(*row,sep="")

Measured memory_bytes: 14324
def main():
    s=set()
    for digit in range(16):
        for i in range(1,1000):
            c=i*10**digit+int('9'*digit or 0)
            if c<10**15:
                s.add(c)
    c=sorted(s)
    for i,n in enumerate(c):
        sn=n/sum(map(int,str(n)))
        for m in c[i+1:i+100]:
            sm=m/sum(map(int,str(m)))
            if sm<sn:
                s.remove(n)
                break
    print(*sorted(s)[:int(input())],sep='\n')
main()

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

int main(){
    int n, k, q;
    cin >> n >> k >> q;

    int memo[100010] = {};

    for(int i = 0;i < q;i++){
        int a;
        cin >> a;
        a--;
        memo[a]++;
    }

    for(int i = 0;i < n;i++){
        if(k-(q-memo[i]) <= 0){
            cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

struct Node {
    int key;
    Node *prev, *next;
} *List;

void init()
{
    List = (Node*)malloc(sizeof(Node));
    List -> next = List;
    List -> prev = List;
}

void insert(int x)
{
    Node *node = (Node*)malloc(sizeof(Node));
    node -> key = x;
    node -> next = List -> next;
    List -> next -> prev = node;
    List -> next = node;
    node -> prev = List;
}

Node* searchList(int x)
{
    Node *p = List -> next;

    while (p != List)
    {
        if (p -> key == x)
        {
            break;
        }
        
        p = p -> next; 
    }

    return p;
}

void deleteNode(Node *p)
{
    if (p == List)
    {
        return;
    }

    p -> prev -> next = p -> next;
    p -> next -> prev = p -> prev;
    
    free(p);
}

void deleteFirst()
{
    deleteNode(List -> next);
}

void deleteLast()
{
    deleteNode(List -> prev);
}

void deleteKey(int key)
{
    deleteNode(searchList(key));
}

void printList()
{
    Node *p = List -> next;

    while ( p != List)
    {
        printf("%d", p -> key);

        if (p->next != List)
        {
            printf(" ");
        }

        p = p -> next;
    }
    
}

int main()
{
    int n,
        key;
    char Command[100];

    init();

    scanf("%d", &n);

    for (int i = 0; i != n; ++i)
    {
        scanf("%s", &Command);
        if (strcmp(Command, "insert") == 0)
        {
            scanf("%d", &key);
            insert(key);
        }
        else if (strcmp(Command, "delete") == 0)
        {
            scanf("%d", &key);
            deleteKey(key);
        }
        else if (strcmp(Command, "deleteFirst") == 0)
        {
            deleteFirst();
        }
        else if (strcmp(Command, "deleteLast") == 0)
        {
            deleteLast();
        }
    }

    printList();
    printf("\n");

    return 0;
}


Measured memory_bytes: 34456
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

ll x, y, a, b, c;
ll d[100005];
ll e[100005];
ll f[200005];
ll g[200005];
ll h[200005];
ll ans;

int main()
{
    scanf("%lld%lld%lld%lld%lld", &x, &y, &a, &b, &c);
    for(ll i = 0; i < a; i++)
    {
        scanf("%lld", &d[i]);
    }
    for(ll i = 0; i < b; i++)
    {
        scanf("%lld", &e[i]);
    }
    for(ll i = 0; i < c; i++)
    {
        scanf("%lld", &f[i]);
    }
    sort(d, d + a, greater<int>());
    sort(e, e + b, greater<int>());
    sort(f, f + c, greater<int>());
    for(ll i = 0, j = 0; i + j < x + y; )
    {
        if(j < y && (d[i] < e[j] || i == x)) g[i + j + 1] = g[i + j] + e[j], j++;
        else g[i + j + 1] = g[i + j] + d[i], i++;
    }
    for(ll i = 1; i <= x + y; i++)
    {
        h[i] = h[i - 1] + f[i - 1];
    }
    for(ll i = 0; i <= x + y; i++)
    {
        ans = max(ans, g[i] + h[x + y - i]);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 6400
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
typedef long long ll;
int GCD(int a, int b) {return b ? GCD(b, a%b): a;}

int main() {
  int N; cin >> N;
  vector<int> a(N); 
  rep(i, N) cin >> a[i];
  vector<int> left(N+1, 0), right(N+1, 0);
  for(int i=0; i<N; i++) {left[i+1]=GCD(left[i], a[i]);};
  for(int i=N-1; i>=0; i--) {right[i]=GCD(right[i+1], a[i]);};
                             
  int res = 0;
    for (int i = 0; i < N; ++i) {
      
        int l = left[i];

        
        int r = right[i+1];

      
        chmax(res, GCD(l, r));
    }
    cout << res << endl;
}

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

int main(){

	unsigned long long int a,b,x;
	cin>>a;
	cin>>b;
	cin>>x;
	if (x<b)
	cout<<(a*x)/b<<endl;
    else
    {
    	cout<<(a*(b-1))/b<<endl;
    }
	

}

Measured memory_bytes: 3624
n,m=map(int,input().split())
ans=0
if(n>=2 and m>=2):
    ans+=(n*(n-1))//2
    ans+=(m*(m-1))//2
elif(n>=2 and m<2):
    ans += (n*(n-1))//2
elif(m>=2 and n<2):
    ans+=(m*(m-1))//2
else:
    pass
print(ans)

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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

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

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
long double eps = 1.0E-14;
#define pow10(n) int(1e##n + n)

void solve()
{
    int N, M;
    cin >> N >> M;
    cout << (N == M ? "Yes" : "No") << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(void){
    ll x,y;
    cin>>x>>y;
    ll ans=0;
    while(x<=y){
        if(x+x<=y) ans++;
        x+=x;
        
    }
    cout<<ans+1<<endl;
}

Measured memory_bytes: 256
grid=[list(map(int,input().split())) for _ in range(3)]

yokosa=[grid[0][i]-grid[0][i-1] for i in range(1,3)]
for y in range(1,3):
  tmp=[grid[y][i]-grid[y][i-1] for i in range(1,3)]
  if yokosa!=tmp:
    print('No')
    exit()
tatesa=[grid[i][0]-grid[i-1][0] for i in range(1,3)]
for x in range(1,3):
  tmp=[grid[i][x]-grid[i-1][x] for i in range(1,3)]
  if tatesa!=tmp:
    print('No')
    exit()
print('Yes')

Measured memory_bytes: 3064
N = int(input())
A = [[0 for i in range(9)] for j in range(9)]
i = 92838
for i in range(1, N+1):
  if i % 10 != 0:
    A[int(str(i)[0])-1][i % 10 - 1] += 1
ans = 0
for i in range(9):
  for j in range(9):
    ans += A[i][j] * A[j][i]
print(ans)

Measured memory_bytes: 73744
#include <algorithm>
#include <cassert>
// #include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
// #include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);
*/
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppiipii;
typedef pair<int, ppiipii> pippiipii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> ppiii;
typedef pair<int, ppiii> pippiii;
typedef pair<int, ll> pill;
typedef pair<int, double> pid;
typedef pair<string, string> pss;
// note to self, the below two triggers someone
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef long double ld;

int n;
int l[100005];

int main() {
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    int t;
    scanf("%d", &t);
    if(t%4==0) {
      l[i] = 2;
    }
    else if(t%2 == 0) {
      l[i] = 1;
    }
    else {
      l[i] = 0;
    }
  }
  sort(l, l+n);
  vector<int> all;
  int lhs = 0;
  int rhs = n-1;
  while(lhs <= rhs) {
    all.push_back(l[lhs++]);
    if(lhs <= rhs) {
      all.push_back(l[rhs--]);
    }
  }
  for(int i = 1; i < all.size(); i++) {
    if(all[i-1] + all[i] < 2) {
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
}


Measured memory_bytes: 1276
P8, P10 = map(int, input().split())


import math
price1_min = math.ceil(P8/0.08)

price1_max = math.floor((P8+1)//0.08)

price2_min = math.ceil(P10/0.10)

price2_max = math.floor((P10+1)//0.10)



if (price1_max >= price2_min) and (price2_max >= price1_min):
    print(max(price2_min, price1_min))
else: 
    print(-1)

Measured memory_bytes: 3060
#include <stdio.h>

int main(){
  int n, m, i, j, l;
  int count = 0;
  int aa[30] = {};

  scanf("%d %d", &n, &m);

  for(i = 0; i < n; i++){
    int k; scanf("%d", &k);
    /* printf("k_%d ... %d\n", i, k); */
    for(j = 0; j < k; j++){
      int a; scanf("%d", &a);
      /* printf("a_%d ... %d\n", j, a); */
      a--;
      aa[a]++;
      /* printf("aa[%d] = %d.\n", a, aa[a]); */
    }
  }

  for(l = 0; l < m; l++){
    if(aa[l] == n) count++;
  }

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

  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define P 1000000007
long mypow(long x,long p){
  if(p==0)return 1;
  if(p%2)return mypow(x,p-1)*x%P;
  else {long a=mypow(x,p/2)%P;return a*a%P;}
}
long inv(long x){
  return mypow(x,P-2);
}
long com(long x,long y){
  long ans=1;
  for(int i=0;i<y;i++)ans=ans*(x-i)%P;
  for(int i=1;i<=y;i++){ans=ans*inv(i)%P;}
  return ans;
}

int main(){
  long X,Y;cin>>X>>Y;
  if((X+Y)%3!=0){cout<<0;return 0;}
  if(Y>X*2||X>Y*2){cout<<0;return 0;}
  cout<<com((X+Y)/3,(Y*2-X)/3)<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<pair<ll, ll>> pll;
 
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
 
const long double PI = acos(-1);
 
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}

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

  ll a, b;
  cin >> a >> b;
  ll ans = 0;
  for(ll i = a; i <= b; i++){
    if(i/10000 == i%10 && i/1000%10 == i/10%10) ans++;
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

#define forn for (ll i = 0; i < n; i++)
#define form for (ll j = 0; j < m; j++)
#define NO cout << "NO\n";
#define YES cout << "YES\n";
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for (ll i = a; i < b; i++)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;

ll gcd(ll a, ll b){
    ll r;
    while (b != 0){
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}


ll *calc_z(string s){
    ll n = s.size();
    ll *z = new ll[n] {0};
    ll l = 0, r = 0;
    for (ll i = 1; i < n; i++){
        if (r >= i) z[i] = min(z[i-l], r-i+1);
        while (z[i]+i < n && s[z[i]] == s[z[i]+i]) z[i]++;
        if (i + z[i] - 1 > r){
            l = i;
            r = i+z[i]-1;
        }
    }
    return z;
}

int find_lower(int *a, int n, int v){
    int l = -1, r = n;

    while (r-l > 1){
        int m = (l+r)/2;
        if (a[m] <= v) l = m;
        else r = m;
    }
    return l;
}

void init(){
}

int bin(int *p, int n, int x){
    int l = 0, r = n-1;
    while (r >= l){
        int m = (l+r)/2;
        if (p[m] == x) return m;
        if (p[m] > x) r = m-1;
        else l = m+1;
    }
    return -1;
}

void solve(){
    int n;
    cin >> n;
    int *a = new int[n];
    forn cin >> a[i];
    int ans = 1;
    int min = a[0];
    for (int i = 1; i < n; i++){
        if (a[i] < min){
            ans++;
            min = a[i];
        }
    }
    cout << ans << '\n';
}

int main(){
    //init();

    ios::sync_with_stdio(false);
    cin.tie(0);

    //ll t; cin >> t; while (t--)
        solve();
    return 0;
}


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

namespace ConsoleApp5
{

    class Program
    {
        static void Main(string[] args)
        {
            String S = Console.ReadLine();
            String[] line = S.Split(' ');
            int N = int.Parse(line[0]);
            int M = int.Parse(line[1]);
            int[] A = new int[N];

            S = Console.ReadLine();
            line = S.Split(' ');

            for (int i = 0; i < N; i++)
            {
                A[i] = int.Parse(line[i]);
            }

            Array.Sort(A);

            int[] B = new int[M];
            int[] C = new int[M];
            List<int> Lank = new List<int>();

            for (int i = 0; i < M; i++)
            {
                S = Console.ReadLine();
                line = S.Split(' ');
                B[i] = int.Parse(line[0]);
                C[i] = int.Parse(line[1]);

            }

            Array.Sort(C, B);
            int count = 0;
            int x = 0;

            for (int i = 0; i < N && x < M; i++)
            {
                if (C[M - 1 - x] > A[i])
                {
                    A[i] = C[M - 1 - x];
                    count++;
                    if (count == B[M - 1 - x])
                    {
                        x++;
                        count = 0;
                    }
                }
                else
                {
                    break;
                }

            }

            long res = 0;

            for (int i = 0; i < N; i++)
            {
                //Console.WriteLine(A[i]);
                res = res + A[i];
            }

            Console.WriteLine(res);
        }
    }
}

Measured memory_bytes: 29280
A, B, C = map(int, input().split())
count = 0

while A%2 == 0 and B%2 == 0 and C%2 == 0:
  if A == B and B == C:
    print(-1)
    exit()
  A, B, C = B//2+C//2, A//2+C//2, A//2+B//2
  count += 1
print(count)
  


Measured memory_bytes: 61736
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vec=vector<ll>;
using mat=vector<vec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
using datas=pair<ll,ll>;
using tdata=pair<datas,ll>;

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll euclidean_gcd(ll a, ll b) {
  if(a<b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)){a=b;b=r;}
  return b;
}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

void printmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  For(i,0,H+2){
    For(j,0,W+2){cout<<a[i*(W+2)+j];}
    cout<<endl;
  }
}
void inputmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  string ss;
  For(i,1,H+1){
    cin>>ss;
    For(j,1,W+1){
      if(ss[j-1]=='#'){
        a[i*(W+2)+j]=1;
      }else{
        a[i*(W+2)+j]=0;
      }
    }
  }
}

int main(){
  ll i,j,N,M,a,b,c;
  cin>>N>>M;
  vector<tdata> elist(M);
  vec d(N,LLONG_MIN),broken(N,0);
  rep(i,M){
    cin>>a>>b>>c;
    elist[i]=tdata(datas(a-1,b-1),c);
  }
  d[0]=0;
  rep(i,N){
    rep(j,M){
      a=elist[j].first.first;
      if(d[a]!=LLONG_MIN){
        b=elist[j].first.second;
        d[b]=max(d[b],d[a]+elist[j].second);
      }
    }
  }
  rep(j,N){
  rep(i,M){
    a=elist[i].first.first;
    b=elist[i].first.second;
    if(d[a]!=LLONG_MIN&&d[b]<d[a]+elist[i].second)broken[b]=1;
  }
  }
  rep(i,N){
    rep(j,M){
      a=elist[j].first.first;
      if(broken[a]){
        b=elist[j].first.second;
        broken[b]=1;
      }
    }
  }
  if(broken[N-1]){
    cout<<"inf"<<endl;
  }else{
    cout<<d[N-1]<<endl;
  }
  return 0;
}

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

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define mem(x,val) memset((x),(val),sizeof(x))
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define PI acos(-1.0) 
#define N 111111

const int INF = 1 << 30 ;
typedef long long ll ;
typedef pair < int , int > pii ;

int main() {
  int a, b, c, d ;
  scanf("%d %d %d %d", &a, &b,&c, &d) ;
  if(a>=d || c>=b) printf("0") ;
  else printf("%d", min(b,d) -max(a,c)) ;
  return 0 ;
}



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

using namespace std;


int main(int argc, char const *argv[])
{
    int n, x, y;
    int inf = 1001001;
    cin >> n >> x >> y;
    x--; y--;
    vector<vector<int>> adj(n);

    for (int i = 0; i < n; i++) {
        if (i - 1 >= 0) {
            adj[i].push_back(i - 1);
        }
        if (i + 1 < n) {
            adj[i].push_back(i + 1);
        }
    }
    adj[x].push_back(y);
    adj[y].push_back(x);

    vector<vector<int>> distance(n, vector<int>(n, inf));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // if (i < x && j < x) {
            //     distance[i][j] = abs(i - j);
            // } else if (i < x && x <= j && j < y) {
            distance[i][j] = min(abs(i - j), abs(x - i) + 1 + abs(y - j));
        }
    }
    vector<int> counts(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dist = distance[i][j];
            counts[dist]++;
        }
    }
    for (int i = 1; i < n; i++) {
        cout << counts[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 16128
#include<cstdio>
using namespace std;
int main(){
    int b,f,r,v;
    int F[10][3][4];
    for(int i=0;i<10;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<4;k++){
                F[i][j][k]=0;
            }
        }
    }
    int num;
    scanf("%d",&num);
    for(int i=0;i<num;i++){
        scanf(" %d %d %d %d",&b,&f,&r,&v);
        F[r-1][f-1][b-1]+=v;
    }
    for(int i=0;i<4;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<10;k++){
                printf(" %d",F[k][j][i]);
                
            }
            printf("\n");
        }
        if(i!=3){
           printf("####################\n"); 
        }
        
    }
}


Measured memory_bytes: 2668
#include <bits/stdc++.h>
using namespace std;
int main ()
{
	int n,a,b,c;
	cin>>n;
	a=n/100;
	b=n/10%10;
	c=n%10;
	if(a==7 || b==7 || c==7)
	cout<<"Yes";
	else
	cout<<"No";
return 0;
}

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

using namespace std;
using ll =long long;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
#define leftunique(a) {SORT(a);(a).erase(unique((a).begin(),(a).end()),(a).end());}
//Write From this Line

int main()
{
	ll a , b, m ;
	cin >> a >> b>> m ; //冷蔵庫、電子、クーポンの枚数
	vector<ll> A(a);
	rep(i,a) cin >>A[i];
	vector<ll> B(b);
	rep(i,b) cin >> B[i];
	//電子レンジの最安と冷蔵庫の最安を保持しておく。
	ll Refr = 1000000;
	ll densi = 1000000; //どっちもの最安値。
	rep(i,a){
		chmin(Refr,A[i]);
	}
	rep(i,b){
		chmin(densi,B[i]);
	}
	ll ans1 = Refr + densi ;
	rep(i,m){
		ll tmp ;
		int x , y , c; 
		cin >> x >> y >> c; 
		--x,--y;
		//A[x]とB[y]を同時に買うとC円安くなる。
		tmp = A[x] + B[y] - c;
		chmin(ans1,tmp);
	}
	cout << ans1 << endl;
}


Measured memory_bytes: 1792
T = input()
l = [t for t in T]

s = len(T)
for i in range(s):
  if l[i] == '?':
    if i == s-1:
      l[i] = 'D'
    elif i == 0 and l[i+1]!='P':
      l[i] = 'P'
    elif i == 0:
      l[i] = 'D'
    elif l[i-1]=='D' and ((l[i+1]=='D')or(l[i+1]=='?')):
      l[i] = 'P'
    else:
      l[i] = 'D'
      
str_changed = "".join(l)
print(str_changed)

Measured memory_bytes: 11160
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <climits>
#include <map>
#include <functional>
#include <cmath>
#include <cassert>

using namespace std;

template<typename T>inline T get(){T x;cin>>x;return x;}

template<typename T>
T gcd(T a, T b)
{
    if (a < b)
        return gcd(b, a);
    else if (a % b == 0)
        return b;
    else
        return gcd(b, a % b);
}

int main()
{
    int n = get<int>();
    int x = get<int>();
    vector<int> xs(n);
    for (int i = 0; i < n; i++)
        xs[i] = abs(get<int>() - x);

    cout << accumulate(xs.begin(), xs.end(), xs[0], gcd<int>)
        << endl;
    return 0;
}

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

import sys
import os

def gcd(a, b):
    # big - small
    while a != b:
        if a > b:
            a, b = b, a
        a, b = b - a, a
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

lst = sys.stdin.readlines()
for s in lst:
    a, b = map(int, s.split())
    G = gcd(a, b)
    L = lcm(a, b)
    print(G, L)

Measured memory_bytes: 7656
#include<bits/stdc++.h>
using namespace std;
 int  main()
{ long long int  n,w;
cin>>n>>w;
long long int  val[n],wt[n];
for(long long int  i=0;i<n;i++)
    cin>>wt[i]>>val[i];
long long int  dp[n+1][w+1]={0};
for(long long int  i=0;i<=n;i++)
    for(long long int  j=0;j<=w;j++)
    dp[i][j]=0;

for(long long int  i=wt[0];i<=w;i++)
    dp[1][i]=val[0];

for(long long int  i=1;i<=n;i++)
{ for(long long int  j=1;j<=w;j++)
    { if(wt[i-1]<=j)
        { dp[i][j]=max(dp[i-1][j-wt[i-1]]+val[i-1],dp[i-1][j]);
            //cout<<i<<" "<<j<<" "<<dp[i-1][j-wt[i-1]]+val[i-1]<<endl;
        }
        else
            dp[i][j]=dp[i-1][j];
    }
}

cout<<dp[n][w]<<endl;
}


Measured memory_bytes: 79104
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000001
using namespace std;

int ans,count_MAX;
int P,Q,Limit,common;

void recursive(int bunshi,int bunbo,int pre_add_bunbo,int bunbo_sum,int count){

	if(Q*bunshi == P*bunbo){
		ans++;
		return;
	}
	if(count == count_MAX)return;

	if(Q*bunshi > P*bunbo)return;

	int next_bunshi,next_bunbo;

	for(int i = pre_add_bunbo; bunbo_sum*i <= Limit; i++){

		next_bunshi = bunshi*i+bunbo;
		next_bunbo = bunbo*i;

		recursive(next_bunshi,next_bunbo,i,bunbo_sum*i,count+1);
	}
}

int main(){

	while(true){
		scanf("%d %d %d %d",&P,&Q,&Limit,&count_MAX);
		if(P == 0 && Q == 0 && Limit == 0 && count_MAX == 0)break;

		ans = 0;

		recursive(0,1,0,1,0);

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

	}

	return 0;
}

Measured memory_bytes: 2616
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    inf=10**9
    n,m=MI()
    kk=[]
    aa=[]
    for _ in range(m):
        k=0
        a,b=MI()
        aa.append(a)
        cc=LI1()
        for c in cc:k|=1<<c
        kk.append(k)
    dp=[inf]*(1<<n)
    dp[0]=0
    for bit in range(1<<n):
        pre=dp[bit]
        if pre==inf:continue
        for a,k in zip(aa,kk):
            nb=bit|k
            dp[nb]=min(dp[nb],pre+a)
    ans=dp[-1]
    if ans==inf:print(-1)
    else:print(ans)

main()


Measured memory_bytes: 3572
N = gets.to_i
A = []
A << gets.strip.split(" ").map(&:to_i)
A << gets.strip.split(" ").map(&:to_i)

sum = 0
sum_l = []
0.upto(N - 1) do |i|
  sum += A[0][i]
  sum_l[i] = sum
end

sum = 0
sum_r = []
(N - 1).downto(0) do |i|
  sum += A[1][i]
  sum_r[i] = sum
end

ans = 0
0.upto(N - 1) do |i|
  a = sum_r[i] + sum_l[i]
  ans = a if a > ans
end

puts ans


Measured memory_bytes: 1788
x, k, d = map(int, input().split())
x = abs(x)

if x >= k*d:
    ans = x - k*d
elif k&1:
    ans = min((x-d)%(2*d), 2*d - (x-d)%(2*d) )
else:
    ans = min(x%(2*d), 2*d - x%(2*d))

print(ans)

Measured memory_bytes: 8960
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a;
    a=n;
    int sum=0;
    while (n%10)
    {
        sum+=n%10;
        n=n/10;
    }
    if (a%sum==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    system("pause");
    return 0;
}

Measured memory_bytes: 504
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

import static java.lang.Integer.parseInt;

/**
 * Problem A: Dirichlet's Theorem on Arithmetic Progressions - Accepted
 */
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;

		// primes
		boolean[] ps = new boolean[1000000 + 1];
		Arrays.fill(ps, true);
		ps[0] = false;
		ps[1] = false;

		for (int i = 2; i <= Math.sqrt(ps.length); i++) {
			if (ps[i]) {
				for (int j = i * 2; j < ps.length; j += i) {
					ps[j] = false;
				}
			}
		}

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			StringTokenizer st = new StringTokenizer(line);

			int a, d, n;
			a = parseInt(st.nextToken());
			d = parseInt(st.nextToken());
			n = parseInt(st.nextToken());
			if ((a | d | n) == 0) break;

			int i = a, c = 0;
			while (true) {
				if (ps[i]) {
					c++;
					if (c == n) break;
				}
				i += d;
			}
			System.out.println(i);

		} // end while
	} // end main
}

Measured memory_bytes: 27424
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
#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 ALL(v) v.begin(), V.end()

int main() {
  int K;
  cin >> K;
  string S;
  cin >> S;
  int s_len = S.length();

  if (s_len > K) {
    REP(i, K) cout << S[i];
    cout << "..." << endl;
  } else {
    cout << S << endl;
  }
}

Measured memory_bytes: 3584
import java.util.*;

 class Main
 {
   public static void main(String args[])
   { 
    input();
   }
   static void input()
   {
     Scanner sc = new Scanner(System.in);
     
     while (true)
     {
       int m = sc.nextInt();//Mid-term test
       
       int f = sc.nextInt();//Final exam
       
       int r = sc.nextInt();//Retest
       
       if (m == -1 && f == -1 && r == -1)break;
       
       output(m,f,r);
     }
   }
   static void output(int m,int f,int r)
   {
     if (m == -1 || f == -1)
     {
       ln("F");
       
       return ;
     }
     if (m + f >= 80)
     {
       ln("A");
       
       return ;
     }
     if (m + f >= 65)
     {
       ln("B");
       
       return ;
     }
     if (m + f >= 50)
     {
       ln("C");
       
       return ;
     }
     if (m + f >= 30)
     {
       if (r >= 50)
       {
         ln("C");
         
         return ;
       }
        else
       {
         ln("D");
         
         return ;
       }
     }
     if (m + f < 30)
     {
       ln("F");
       
       return ;
     }
   }
   static void ln(String s)
   {
     System.out.println(s);
   }
 }
    


Measured memory_bytes: 26564
#include<bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<=n;i++)
#define rep2(i,k,n) for(int i=k;i>=n;i--)
using namespace std;
const int N=3007;
const int mod=1e9+7;
void upd(int& x,int y){x+=y;if(x>=mod)x-=mod;}
int f[2][N][2],op,n,m,ans=0;
int main(){
	scanf("%d%d",&n,&m);
	
	rep(i,0,n)f[op][i][0]=1;
	int res;
	rep(i,1,m){
		memset(f[op^1],0,sizeof(f[op^1]));
		rep(j,0,n){
			rep(k,0,1)
			if((res=f[op][j][k])){
				if(!j)upd(f[op^1][j+1][1],res),upd(f[op^1][j][1],res);
				else if(j==1){
					if(j!=n)upd(f[op^1][j][k],res);
					upd(f[op^1][j+1][k],res);
					
					upd(f[op^1][j][1],res);
					upd(f[op^1][j-1][1],res);
				}else{
					upd(f[op^1][j-1][k],res);
					if(j!=n)upd(f[op^1][j][k],res);
					upd(f[op^1][j][k],res);
					upd(f[op^1][j+1][k],res);
				}
			}
		}
		op^=1;
	}
	rep(j,0,n)upd(ans,f[op][j][1]);
	printf("%d\n",ans);
}

Measured memory_bytes: 256
// AtCoder Regular Contest 095 - Problem D: Binomial Coefficients (https://arc095.contest.atcoder.jp/tasks/arc095_b)
#include <iostream>
 
#include <map>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
using ll = long long;
using ii = pair<ll, ll>;
 
const ll MAX { 200010 };
int as[MAX];
 
 
int main()
{
    ios::sync_with_stdio(false);
 
    int N;
    cin >> N;
 
    for (int i = 0; i < N; ++i)
        cin >> as[i];
 
    sort(as, as + N);
 
    int ai = as[N - 1];
    int aj = -1, dist = 2000000010;
 
    for (int i = 0; i < N - 1; ++i)
    {
        int k = min(as[i], ai - as[i]);
 
        if (ai/2 - k < dist)
        {
            aj = as[i];
            dist = ai/2 - k;
        }
    }
 
    cout << ai << " " << aj << endl;
 
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
typedef long long ll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

//aとbのうち大きい値をaとして採用する
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false;}

int main(){
    int N_MAX = 110000;
    int n; cin>>n;
    vector<int>a(N_MAX);
    vector<int>b(N_MAX);
    vector<int>c(N_MAX);
    rep(i,n)cin>>a[i]>>b[i]>>c[i];
    vector <vector<ll>> dp(N_MAX,vector<ll>(3,0));

    rep(i,n){
        chmax(dp[i+1][0],dp[i][1]+a[i]);
        chmax(dp[i+1][0],dp[i][2]+a[i]);
        chmax(dp[i+1][1],dp[i][0]+b[i]);
        chmax(dp[i+1][1],dp[i][2]+b[i]);
        chmax(dp[i+1][2],dp[i][0]+c[i]);
        chmax(dp[i+1][2],dp[i][1]+c[i]);
    }

    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]))<<endl;return 0;
}


Measured memory_bytes: 7552
//Wrong answer on test inf.
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
#define inf 1000000001
#define pii pair<int,int>
#define fi first
#define se second
#define y1 y1___
using namespace std;
ll read(){
	char ch=getchar();ll x=0;int op=1;
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') op=-1;
	for (;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
	return x*op;
}
#define N 500005
int n,r,c,tot,xb,a[N];pii p[N];
bool chk(int x,int y){
    return (x==0||x==r)||(y==0||y==c);
}
int get(int x,int y){
    if (y==0) return x;
    if (x==r) return y+r;
    if (y==c) return r+c+r-x;
    return 2*r+c+c-y;
}
struct bit{
    int t[N];
    void add(int x){
        for (int i=x;i<=xb;i+=i&-i) t[i]++;
    }
    int qry(int x){
        int ret=0;
        for (int i=x;i;i-=i&-i) ret+=t[i];
        return ret;
    }
}tr;
int main(){
    r=read(),c=read(),n=read();
    // cerr<<get(3,5)<<'\n';
    rep (i,1,n){
        int x1=read(),y1=read(),x2=read(),y2=read();
        if (chk(x1,y1)&&chk(x2,y2)){
            p[++tot]=pii(get(x1,y1),get(x2,y2));
            // cerr<<"i="<<i<<": "<<p[tot].fi<<','<<p[tot].se<<'\n';
        }
    }
    rep (i,1,tot) if (p[i].fi>p[i].se) swap(p[i].fi,p[i].se);
    sort(&p[1],&p[tot+1]);
    rep (i,1,tot) a[++xb]=p[i].fi,a[++xb]=p[i].se;
    sort(&a[1],&a[xb+1]);
    rep (i,1,tot){
        p[i].fi=lower_bound(&a[1],&a[xb+1],p[i].fi)-a;
        p[i].se=lower_bound(&a[1],&a[xb+1],p[i].se)-a;
    }
    int mxr=-1;
    rep (i,1,tot){
        if (tr.qry(p[i].se)-tr.qry(p[i].fi-1)>0){puts("NO");exit(0);}
        tr.add(p[i].se);
    }
    puts("YES");
    return 0;
}

Measured memory_bytes: 5760
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}
#define trace1(x)			 	 cerr<<#x<<": "<<x<<endl
#define trace2(x, y)		 	 cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)		 	 cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)	 	 cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)	 cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,W;
	cin >> n >> W;
	ll weight[n+1],value[n+1];
	rep(i,1,n+1){
		cin >> weight[i] >> value[i];
	}
	weight[0]=0;
	value[0]=0;
	ll dp[n+1][W+1];
	rep(i,0,n+1){
		rep(j,0,W+1){
			dp[i][j]=0;
		}
	}

	rep(i,1,n+1){
		rep(j,0,W+1){
			if(weight[i]>j){
				dp[i][j]=dp[i-1][j];
			}
			else{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
			}
		}
	}
	cout << dp[n][W];
	return 0;
}

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

#define sz(s) (ll)(s.size())
#define all(x) (x.begin(), x.end())

#define pb push_back
#define pf push_front
#define F first
#define S second
#define ort1 exit(0);
#define nl endl
#define db double

#define TL clock() / (double)CLOCKS_PER_SEC
#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;


const double pi = acos(-1.0);
const double eps = 1e-9;
const int mod = 1e9 + 7;
const ll INF = 1e12 + 1;
const int N = 1e2 + 9;

string s, t;
int x;

int main()
{
    cin >> s >> t;
    if(s.size() != t.size()){
        cout << "No";
        ort1
    }
    x = t.size();
    while(x > 0){
        x--;
        t.pb(t[0]);
        t.erase(t.begin());
        if(t == s){
            cout << "Yes";
            return 0;
        }
    }

    cout << "No";

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
     
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,a,b)    for(int i=a;i<b;i++)
#define repn(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define mp  make_pair
#define all(v) (v).begin(), (v).end()
#define hell 1000000007  
#define hell2 998244353 

int solve(){
    int n,l,r;
    cin>>n;
    int a[n],b[n];
    rep(i,0,n) cin>>a[i]>>b[i];
    sort(a,a+n);sort(b,b+n);
    l=a[n/2];r=b[n/2];
    if(n%2==0) l=l+a[n/2-1],r=r+b[n/2-1];
    cout<<r-l+1;
    return 0;
}   
     
signed main(){
    IOS;
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout<<"\n";
      // cout<<" * "<<t<<"\n";
    }
//    return 0;
} 

Measured memory_bytes: 6748
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int sum = 0;
  for(int i=1; i<n; ++i) if(s[i] == 'E') ++sum;
  int ans = sum;
  for(int i=1; i<n; ++i){
    int tmp = 0;
    if(s[i-1] == 'W') ++tmp; 
    if(s[i] == 'E') --tmp;
    sum += tmp;
    ans = min(ans, sum); 
  }
  cout << ans << endl;
}

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

bool solve() {
  int a, b;
  string s;
  cin >> a >> b >> s;

  if (a + b != s.size() - 1) {
    return false;
  }
  
  bool ok = true;
  for (int i=0; i<s.size(); i++) {
    if (i==a) {
      ok &= s[i] == '-';
    } else {
      ok &= (s[i] >= '0' && s[i] <= 'z'); 
    }
  }
  
  return ok;
}

int main() {
  cout << (solve() ? "Yes" : "No") << endl;
  return 0;
}


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

int main(){
  string s;
  cin >>s;
  string s1, s2;
  for(int i = 0; i<4; i++) s1 += s[i];
  for(int i = 4; i<12; i++) s2 += s[i];
  cout << s1 << " " << s2 << endl;
  return 0;
}

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

struct UnionFind
{
    vector<int> data;
    UnionFind(int size) : data(size, -1) {}
    bool unionSet(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x != y)
        {
            if (data[y] < data[x])
                swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y)
    {
        return root(x) == root(y);
    }
    int root(int x)
    {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x)
    {
        return -data[root(x)];
    }
};

int main()
{
    long long N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    for (int i = 0; i < M; i++)
    {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }

    UnionFind uf(N);
    long long ans = N * (N - 1) / 2;
    vector<long long> ansv(M);
    ansv[M - 1] = ans;

    for (int i = M - 1; i >= 1; i--)
    {
        if (!uf.findSet(A[i], B[i]))
        {
            ans -= uf.size(A[i]) * uf.size(B[i]);
            uf.unionSet(A[i], B[i]);
        }
        ansv[i - 1] = ans;
    }

    for (int i = 0; i < ansv.size(); i++)
    {
        cout << ansv[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 3328
h, w, n = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(n)]

for i in range(n):
    for j in range(2):
        A[i][j] -= 1

D = {}

for i in range(n):
    # print(D)
    for j in range(-1, 2):
        for k in range(-1, 2):
            if 1 <= A[i][0]+j <= h-2 and 1 <= A[i][1]+k <= w-2:
                try:
                    D[(A[i][0]+j, A[i][1]+k)] += 1
                except:
                    D[(A[i][0]+j, A[i][1]+k)] = 1

ANS = [0] * 10
for i in D.values():
    ANS[i] += 1
ANS[0] = (h-2) * (w-2) - sum(ANS[1:])

for i in ANS:
    print(i)

Measured memory_bytes: 160376
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
signed main(){
  ll n,cnt=0,tmp;
  cin >> n;
  ll a[n];
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  cnt = a[n-1];
  tmp=a[n-1]-1;
  for(int i=n-2;i>0;i--){
    if(a[i]<tmp){
      cnt=-1;
      break;
    }else{
      if(a[i]>tmp){
        cnt += a[i];
        tmp=a[i]-1;
      }else{
        tmp--;
      }
    }
  }
  if(tmp>0||a[0]>0){
    cnt=-1;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 1792