akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  int H,W,A,B;
  cin >> H >> W >> A >> B;
  rep(i,H) {
    rep(j,W) {
      if(i < B && j < A) {
        cout << 0;
      } else if(i < B) {
        cout << 1;
      } else if(j < A) {
        cout << 1;
      } else {
        cout << 0;
      }
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1280
// This code was written in Qt
#pragma GCC optimize("O3")
#define first x
#define second y
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;typedef unsigned long long ull;
enum {MOD0 = 1000000000, MOD7 = 1000000007, MOD9 = 1000000009};
inline long nano_time() {return chrono::high_resolution_clock::now().time_since_epoch().count();}
#ifndef CrafterKolyan
#define endl '\n'
#endif

int x[100000];

main() {
#ifndef CrafterKolyan
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    int ans = INT_MAX;
    for (int i = 0; i + k - 1 < n; ++i) {
        ans = min(ans, abs(x[i]) + abs(x[i + k - 1] - x[i]));
    }
    for (int i = k - 1; i < n; ++i) {
        ans = min(ans, abs(x[i]) + abs(x[i] - x[i - (k - 1)]));
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
n = int(raw_input())
a = map(int, raw_input().split())
cnt2 = 0
cnt4 = 0
for i in xrange(n):
    if a[i] % 4 == 0:
        cnt4 += 1
    elif a[i] % 2 == 0:
        cnt2 += 1
m = n - cnt4 - cnt2
if cnt2 == 0:
    if m - 1 <= cnt4:
        print "Yes"
    else:
        print "No"
else:
    if m <= cnt4:
        print "Yes"
    else:
        print "No"


Measured memory_bytes: 11296
N, K =list(map(int, input().split()))
# N, K = 15, 14
l = list(map(int, input().split()))
# l = [50, 26, 27, 21, 41, 7, 42, 35, 7, 5, 5, 36, 39, 1, 45]
sorted_l = sorted(l, reverse=True)
print(sum(sorted_l[:K]))


Measured memory_bytes: 2940
#include <algorithm>
#include <array>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <string>
#include <string_view>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

int64_t read_int() {
    int64_t ret = 0, sgn = 1;
    int ch = getchar_unlocked();
    while (isspace(ch)) { ch = getchar_unlocked(); }
    if (ch == '-') { sgn = -1; ch = getchar_unlocked(); }
    for (; isdigit(ch); ch = getchar_unlocked())
        ret = (ret * 10) + (ch - '0');
    ungetc(ch, stdin);
    return sgn * ret;
}

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()

template <typename T> inline void assign_min(T& x, const T& value) noexcept { x = min(x, value); }
template <typename T> inline void assign_max(T& x, const T& value) noexcept { x = max(x, value); }

constexpr char LF = '\n';

//-------------------------------------------------------------------------------------------------

int main() {
    auto N = read_int();
    map<int64_t, int64_t> A; // 値 → 個数
    REP(i, N) {
        auto a = read_int();
        ++A[a];
    }

    int64_t sum = 0;
    for (auto [value, cnt] : A) {
        sum += value * cnt;
    }

    auto Q = read_int();
    REP(q, Q) {
        auto B = read_int();
        auto C = read_int();
        auto cnt = A[B];
        sum -= B * cnt;
        sum += C * cnt;
        A[C] += cnt;
        A.erase(B);
        cout << sum << LF;
    }
}


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

#define FOR(i,a,n) for (int i = a; i < (int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define whole(f,x,...) ([&](decltype((x)) whole) { \
    return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
template<typename T> bool chmin(T &a, const T &b) {if (a > b) { a = b; return true; }return false;}
template<typename T> bool chmax(T &a, const T &b) {if (a < b) { a = b; return true; }return false;}

using ll = int_fast64_t;

constexpr ll INF = (1e9);
constexpr ll MOD = (1e9+7);

int main() {
  int n; cin >> n;
  vector<ll> a(n); REP(i,n) cin >> a[i];
  vector<ll> s(n+1, 0), xo(n+1, 0);
  REP(i,n) {
    s[i+1] = s[i] + a[i];
    xo[i+1] = xo[i] ^ a[i];
  }
  ll ans = 0;
  ll l = 0, r = 1;
  while(r <= n) {
    while(s[r]-s[l] != (xo[r] ^ xo[l])) l++;
    ans += r-l;
    r++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 4992
/*
    Problem 95
    https://atcoder.jp/contests/abc149/tasks/abc149_b
*/
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    ll A, B, K;
    cin >> A >> B >> K;
    ll tmp = A;
    A = max(0LL, A - K);
    K = max(0LL, K - tmp);
    B = max(0LL, B - K);
    cout << A << ' ' << B << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  
  int N;
  cin >> N;
   vector<int64_t> vecX(N+1);
  vecX.at(0) = 2;
  vecX.at(1) = 1;
  
  if(N > 1){
    for(int i = 2 ; i < N+1 ; i++){
      vecX.at(i) = vecX.at(i-1) + vecX.at(i-2);
    }
  }
  cout << vecX.at(N) << endl;
}

Measured memory_bytes: 256
K = int(input())    
count = 0
i = 0
j = 0

if K == 2:
    count = 1

elif K == 3:
    count = 2

elif K > 3:
    while i < K:
        i += 1
        j = i + 1

        while j <= K:
            
            count += 1
            
            j += 2
            
print(count)

Measured memory_bytes: 9156
#include<stdio.h>

int main(){
  int n, m, x, y, z;

  while(1){
    scanf("%d %d", &n, &m);
    if(n == 0 && m == 0) break;

    x = m - n;
    z = x / 1000;
    x -= z * 1000;
    y = x / 500;
    x -= y * 500;
    x /= 100;

    printf("%d %d %d\n", x, y, z);
  }

  return 0;
}

Measured memory_bytes: 0
package main

import (
	"fmt"
	//"sort"
	//"strconv"
	//"strings"
	"bufio"
	"os"
	"strconv"
	"math"
)

func main() {
	//input
	var n int
	fmt.Scan(&n)
	var a [100]int
	var b []int

	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := 0; i < n-1; i++ {
		sc.Scan()
		a, _ := strconv.Atoi(sc.Text())
		b = append(b,a)
	}
	if n == 2 {
		fmt.Println(b[0]*2)
	}else{
		lastA := b[n-2]
		for i := n-2; i >= 1; i-- {
			a[i] = int(math.Min(float64(b[i]),float64(b[i-1])))  
		}
		//firstA := int(math.Max(float64(b[0]),float64(b[1])))
		firstA := b[0]
		sum := 0
		for _, x := range a {
			sum += x
		}
		fmt.Println(sum+lastA+firstA)
	}
	//
	//fmt.Print(maxcount)
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define END '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define trace(x) cerr<<x<<END;
#define loop(i, a, b) for(int i = (a); i < (b); i++)
#define loopb(i, b, a) for(int i = (b); i > (a); --i) 
const int mod = 1e9+7;
const int mod1 = 998244353;
const int inf = INT_MAX;


void solve()
  {
    string s,t;
    cin>>s>>t;
    map<char,set<int>> mp;
    int sz = s.size();
    loop(i,0,sz)
      mp[s[i]].insert(i+1);
    int last = 0,ans = 0;
    int n = t.size();
    loop(i,0,n)
     {
      //cerr<<ans<<" "<<last<<END;
      if(mp[t[i]].empty())
         {
          cout<<-1;
          return;
         }
      auto it = mp[t[i]].upper_bound(last);
      if(it == mp[t[i]].end())
         {
          ans += sz + *mp[t[i]].begin() - last;
          last = *mp[t[i]].begin();
         }
      else
         {
          ans += *it - last;
          last = *it;
         }
     }
      //cerr<<ans<<" "<<last<<END;

    cout<<ans;
  } 
signed main()
 {
  
     solve();
  //cerr<<END<<1.0*clock();
  return 0;
} 

Measured memory_bytes: 5248
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,readline().split())
ab = list(map(int,read().split()))

target = [k]
for i in range(1,30):
    if((k>>i)&1):
        target.append(( k-(1<<i)) | ((1<<i)-1) )

ans = 0
for i in target:
    val = 0
    it = iter(ab)
    for a,b in zip(it,it):
        if( a - (i&a) == 0 ):
            val += b
    ans = max(ans,val)

print(ans)

Measured memory_bytes: 105600
//13
#include<iostream>

using namespace std;

int main(){
  for(int r,c,q;cin>>r>>c>>q,r|c|q;){
    int a[50000],b[50000],o[50000];
    for(int i=0;i<q;i++){
      cin>>a[i]>>b[i]>>o[i];
    }
    bool aw[2][50001]={};
    int rs[2]={c,r};
    int an=0;
    for(int i=q-1;i>=0;i--){
      if(!aw[a[i]][b[i]]){
	if(o[i]){
	  an+=rs[a[i]];
	}
	rs[a[i]^1]--;
	aw[a[i]][b[i]]=true;
      }
    }
    cout<<an<<endl;
  }
  return 0;
}
	
      

Measured memory_bytes: 1848
// Wall
// 所要時間 6分
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define all(v) v.begin(), v.end()
using ll = long long;
using P = pair<int, int>;

int main() {

    int h, w;
    cin >> h >> w;
    vector<vector<int>> c(10, vector<int>(10));
    rep(i, 10){
        rep(j, 10){
            cin >> c[i][j];
        }
    }

    rep(k, 10){
        rep(i, 10){
            rep(j, 10){
                c[i][j] = min(c[i][j], c[i][k]+c[k][j]);
            }
        }
    }

    int ans = 0;
    rep(i, h){
        rep(j, w){
            int a;
            cin >> a;
            if(a != -1){
                ans += c[a][1];
            }
        }
    }
    cout << ans << endl;

    return 0;
}

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

int main(){
    long N,K; cin>>N>>K;
    
    double sum = 0;
    rep(i, N){
        long s = i+1;
        int j=0;
        while(s < K){
            s *= 2;
            j++;
        }
        sum += 1.0/N * pow(0.5, j);
    }

    cout << fixed << setprecision(10) <<sum << endl;
}


Measured memory_bytes: 4052
#include <stdio.h>

#define N 2000001
#define M 10000

int  B[N], C[M];

void CountingSort(int A[N], int k, int n);
  
 


int main(){
  
  int i,n, max = 0, A[N];
  scanf("%d", &n);

  for(i = 1 ; i <=n ; i++ ){
    
    scanf("%d", &A[i]);

    if(A[i] > max) max = A[i];
     
  }
  

CountingSort(A, max, n);

 return 0;
}   
  
void CountingSort(int A[N], int k, int n){
  
  int i, j;
  
 
  for(i = 0 ; i <= k ; i++){
    
    C[i] = 0;
  
  }
  
    for(j = 1 ; j <= n ; j++){
      
      C[A[j]] = C[A[j]]+1;
      
    }

  
  
  for(i = 1 ; i <= k ; i++){
    
    C[i] = C[i] + C[i - 1];
  }
  
  for(j = n ; j >= 1 ; j--){
    
    B[C[A[j]]] = A[j];
    C[A[j]] = C[A[j]]-1;
    
  }
  
  for(i = 1 ; i <= n ; i++){
  printf("%d", B[i]);
  if (i < n)printf(" ");
   }
  printf("\n");
}
 

Measured memory_bytes: 16268
#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

ll m[100][3];
ll N;

int main(){
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<3;j++) cin >> m[i][j];
    }
    for(int i=0;i<N;i++){
        if(m[i][2] != 0){
            for(int j=0;j<3;j++){
                ll n = m[0][j];
                m[0][j] = m[i][j];
                m[i][j] = n;
            }
            break;
        }
    }
    for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){
            ll H = m[0][2] + abs(i-m[0][0]) + abs(j-m[0][1]);
            bool f = true;
            for(int k=1;k<N;k++){
                if(m[k][2] == 0){
                    if(H > abs(i-m[k][0]) + abs(j-m[k][1])){
                        f = false;
                        break;
                    }
                }else if(H != m[k][2] + abs(i-m[k][0]) + abs(j-m[k][1])){
                    f = false;
                    break;
                }
            }
            if(f){
                cout << i << " " << j << " " << H << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
n = int(input())
jobs = [list(map(int, input().split())) for i in range(n)]
jobs = sorted(jobs, key=lambda x: x[1])

elapsed_time = 0
possible = True
for job in jobs:
  if elapsed_time + job[0] <= job[1]:
    elapsed_time += job[0]
  else:
    possible = False
    break

if possible:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 55252
import sys
input = sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    tree = {i:[] for i in range(N)}
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges.append((a, b))
        tree[a].append(b)

    ans = {}
    frontier = deque([(1,0)])
    while frontier:
        u, prev_color = frontier.pop()
        if tree.get(u) is None:
            continue

        over_color = len(tree[u])+1
        for i, v in enumerate(tree[u], 1):
            color = i if i != prev_color else over_color
            ans[u, v] = color
            frontier.appendleft((v, color))

    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])


    
main()

Measured memory_bytes: 53892
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program 
{
  static void Main() 
  {
    int[] input = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
    int H = input[0];
    int W = input[1];
    int N = input[2];
    
    List<long> list = new List<long>();
    for (int i = 0; i < N; i++)//黒い箇所全て
    {
      int[] inputb = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
      for (int j = inputb[0] - 1; j <= inputb[0] + 1; j++)//黒いxの前後3箇所
      {
        for (int k = inputb[1] - 1; k <= inputb[1] + 1; k++)//黒いyの前後3箇所
        {
          if (j >= 2 && j <= H - 1 && k >= 2 && k <= W - 1)//中央に9周囲が存在するならば
          {
            list.Add((long)(j-1)*W + k);//マスの番号（1~）
          }
        }
      }
    }
    list.Sort();
    long temp = 0;
    int num = 0;
    long[] ans = new long[10];
    ans[0] = (long)(H-2) * (W-2);//黒がない場合で解答を初期化
            
    for (int i = 0; i < list.Count; i++)//リストを全探索
    {
      if (list[i] != temp)//座標が変わったならば
      {
        if (temp != 0) 
        {
          ans[num]++;
          ans[0]--;
        }
        temp = list[i];
        num = 1;
      }else num++;//同じ座標ならば       
    }
    ans[num]++;
    ans[0]--;
    
    for (int i = 0; i < 10; i++) Console.WriteLine(ans[i]);
  }
}

Measured memory_bytes: 30536
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int a[n],b[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b,b+n);
    int k=b[n/2-1];
    for(int i=0;i<n;i++)
        if(a[i]>k)
            printf("%d\n",b[n/2-1]);
        else printf("%d\n",b[n/2]);
    return 0;
}


Measured memory_bytes: 3712
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("0"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;



int main() {
  int n;
  scanf("%d",&n);
  vi a(n);
  rep(i,n) scanf("%d",&a[i]), --a[i];
  int ans = 0;
  rep(i,n) {
    if (a[i] == i) continue;
    if (a[a[i]] == i) ans++;
  }
  ans >>= 1;
  cout<<ans<<endl;
  return 0;
}







Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
void Main()
{
    ll n, K;
    cin >> n >> K;

    vector<ll> A(n);
    rep(i, n) cin >> A[i];
    rep(i, n) A[i]--;
    
    vector<int> seen(n, -1);
    ll cur = 0;
    bool skipped = false;
    rep (i, K) {
        seen[cur] = i;
        cur = A[cur];
        if (skipped == false && seen[cur] >= 0) {
            ll loopLen = 1 + i - seen[cur];
            i += (K - i - 1) / loopLen * loopLen;
            skipped = true;
        }
    }

    put(1 + cur);
}
signed main(){ Main();return 0;}

Measured memory_bytes: 5584
sx, sy, tx, ty = map(int, input().split())

dx, dy = tx - sx, ty - sy

path = ''
path += 'U' * dy + 'R' * dx
path += 'D' * dy + 'L' * dx
path += 'L' + 'U' * (dy + 1) + 'R' * (dx + 1) + 'D'
path += 'R' + 'D' * (dy + 1) + 'L' * (dx + 1) + 'U'

print(path)

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

int w, d, n;
vector<vector<int>> upper(52, vector<int>(52, 10000));
vector<vector<int>> lower(52, vector<int>(52, -10000));

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

    cin >> w >> d >> n;
    while (n--) {
        int x, y, z; cin >> x >> y >> z;
        for (int i = 1; i <= w; i++) {
			for (int j = 1; j <= d; j++) {
                int man_dist = abs(i - x) + abs(j - y);
				upper[i][j] = min(upper[i][j], z + man_dist);
				lower[i][j] = max(lower[i][j], z - man_dist);
			}
        }
    }

    int ans = 0;
    for (int i = 1; i <= w; i++) {
		for (int j = 1; j <= d; j++) {
            if (lower[i][j] <= upper[i][j]) {
				ans += lower[i][j];
            } else {
				cout << "No\n";
				exit(0);
            }
		}
    }
    cout << ans << '\n';

    return 0;
}



Measured memory_bytes: 3236
MOD = 1000000007
n, k = map(int, input().split())
rsw = [0]*(n+2)
for i in range(1,n+2):
    rsw[i] = (rsw[i-1]+i-1)%MOD
rsw_e = [0]*(n+2)
for i in range(1,n+2):
    rsw_e[i] = (rsw_e[i-1]+n-(i-1))%MOD
res = 0
for i in range(k,n+2):
    start = rsw[i]
    end = rsw_e[i]
    res += (end-start+1)%MOD
print(res%MOD)

Measured memory_bytes: 24488
def main():
    n = int(input())
    t, a = map(int, input().split())
    hs = list(map(int, input().split()))
    diff = float("inf")
    for i in range(n):
        temp = t - hs[i] * 0.006
        if diff > abs(temp - a):
            diff = abs(temp - a)
            ans = i + 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

int dp[3005][3005];

int main(){
  int N, T;
  cin >> N >> T;
  vector<pair<int,int>> v;
  rep(i,N){
    int a, b;
    cin >> a >> b;
    v.emplace_back(a,b);
  }
  sort(ALLOF(v));

  rep(i,3005) rep(j,3005) dp[i][j] = -1;
  dp[0][0] = 0;
  
  rep(i,N){
    rep(j,T){
      dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
      dp[i+1][min(T, j+v[i].first)] = max(dp[i+1][min(T, j+v[i].first)], dp[i][j] + v[i].second);
    }
  }
  int ret = 0;
  rep(i,N+1){
    rep(j,T+1){
      ret = max(ret, dp[i][j]);
    }
  }

  cout << ret << endl;
  
  return 0;
}



Measured memory_bytes: 35712
from heapq import heappush, heappop

N, M = map(int, input().split())

edges = [[] for _ in range(N)]
for i in range(1, N):
    edges[i].append((i - 1, 0))

for _ in range(M):
    l, r, c = map(int, input().split())
    l -= 1
    r -= 1
    edges[l].append((r, c))

que = [(0, 0)]
minDist = [float('inf')] * N
while que:
    d, now = heappop(que)
    if d >= minDist[now]:
        continue
    minDist[now] = d
    for to, cost in edges[now]:
        dist = d + cost
        if minDist[to] > dist:
            heappush(que, (dist, to))

ans = minDist[N - 1]
print(-1 if ans == float('inf') else ans)

Measured memory_bytes: 45484
// All Heil Fire Lord Zuko

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

string s;
int k;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> s;
    cin >> k;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (s[i] != 'a') {
            if (k >= 'z' - s[i] + 1) {
                k -= 'z' - s[i] + 1;
                s[i] = 'a';
            }
        }
    }
    s[n - 1] = (s[n - 1] - 'a' + k) % 26 + 'a';
    cout << s << "\n";
    return 0;
}


Measured memory_bytes: 592
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	long long int n, m;
	cin >> n >> m;
	long long int a, b;
	vector<long long int> p;
	vector<long long int> q;
	for (long long int i = 0; i < m; i++) {
		cin >> a >> b;
		if (a == 1) {
			p.push_back(b);
		}
		else if (b == n) {
			q.push_back(a);
		}
	}
	sort(p.begin(), p.end());
	sort(q.begin(), q.end());
	bool h = false;
	for (long long int i = 0; i < p.size(); i++) {
		vector<long long int>::iterator ite = lower_bound(q.begin(), q.end(), p[i]);
		if (ite != q.end() && *(ite) == p[i]) {
			h = true;
		}
	}
	if (h) {
		cout << "POSSIBLE" << endl;
	}
	else {
		cout << "IMPOSSIBLE" << endl;
	}
	return 0;
}

Measured memory_bytes: 1984
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x)  (int)x.size()
#define en     '\n'
#define sp     ' '
#define in(v)  for(auto &a: v)cin >> a;
#define out(v) for(auto &a: v)cout << a << sp;cout << en;

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

    int n, x, y, i;
    cin >> n;
    vector < int > v1, v2;
    for(i = 0;i < n;i++){
        cin >> x >> y;
        v1.push_back(x);
        v2.push_back(y);
    }
    x = 0;
    for(i = 0;i < n;i++){
        if(v1[i] == v2[i])x++;
        else x = 0;
        if(x == 3)break;
    }
    if(x == 3)cout << "Yes\n";
    else cout << "No\n";
    return 0;
}


Measured memory_bytes: 3656
n,K=map(int,input().split())
data=[]
for i in range(n):
    x,y=map(int,input().split())
    data.append((x,y))
y_sorted=sorted(data,key=lambda x:x[1])
x_sorted=sorted(data,key=lambda x:x[0])


ans=10**20
len_data=len(data)
for i in range(len_data):
    left=x_sorted[i]
    for j in range(len_data):
        down=y_sorted[j]
        if(left[1] < down[1] or down[0] < left[0]):
             continue
        for k in range(j+1,len_data):
            upp=y_sorted[k]
            if(upp[1] < left[1] or upp[0] < left[0]):
                continue
            for l in range(i+1,len_data):
                right=x_sorted[l]
                if( ans <=(right[0] - left[0]) * (upp[1] -down[1])):
                    break
                if((right[0] - left[0]) * (upp[1] -down[1])==0):
                    continue
                if(right[1] < down[1] or right[1] > upp[1] \
                 or right[0] < down[0] or right[0] < upp[0]):
                    continue
                tmp=0
                for m in range(len_data):
                    now=x_sorted[m]
                    if(down[1] <= now[1] <= upp[1] and left[0] <= now[0] <= right[0]):
                        tmp+=1
                        if(tmp==K):
                            ans= min( [ans, (right[0] - left[0]) * (upp[1] -down[1])])
                            break




print(ans)

Measured memory_bytes: 3192
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
int n;
ll a[N][N],v1[N*2],v2[N*2];
vector<int>pri;
int vis[100005];

void Init() {
  for(int i=2;i<=100000;i++) {
    if(vis[i]) continue;
    vis[i]=1;
    pri.push_back(i);
    for(int j=i*2;j<=100000;j+=i) vis[j]=1;
  }
}

ll Lcm(ll a,ll b) {
  ll G=__gcd(a,b);
  return a/G*b;
}

int Judge(int x,int y) {
  if(x<1||x>n||y<1||y>n) return 0;
  return 1;
}

int main() {
  Init();
  scanf("%d",&n);
  if(n==2) {
    puts("2 7 \n13 3");
    return 0;
  }
  int nw=0;
  for(int i=1;i<=n;i++) v1[i]=pri[nw],nw++;
  for(int i=1;i<=n;i++) v2[i]=pri[nw],nw++;
  for(int i=1;i<=n;i++) {
    int st=i&1?1:2;
    for(int j=st;j<=n;j+=2) {
      int A=(i+j)/2,B=(j-i+n+1)/2;
      //printf("%d %d %d %d\n",i,j,A,B);
      a[i][j]=v1[A]*v2[B];
    }
  }
  //cerr<<"GG"<<endl;
  /*
  for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) {
      printf("%lld%c",a[i][j]," \n"[j==n]);
    }
  }
  */
  for(int i=1;i<=n;i++) {
    int st=i&1?2:1;
    for(int j=st;j<=n;j+=2) {
      ll V=1;
      for(int k=0;k<4;k++) {
	int nx=i+dx[k],ny=j+dy[k];
	if(Judge(nx,ny)) {
	  V=Lcm(V,a[nx][ny]);
	}
      }
      a[i][j]=V+1;
    }
  }
  for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) {
      printf("%lld%c",a[i][j]," \n"[j==n]);
    }
  }
  return 0;
}


Measured memory_bytes: 5632
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, W = [int(x) for x in stdin.readline().rstrip().split()]
wv = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

# 重さiでの価値の最大
# 品物の重複選択を許さない
dp = [[0] * (W+10) for _ in range(N+10)]

for i in range(N):
    weight, value = wv[i]
    dp[i+1] = dp[i][:]
    for j in range(weight, W+1):
        dp[i+1][j] = max(dp[i][j], dp[i][j-weight]+value)

print(dp[N][W])


Measured memory_bytes: 191924
N,K = map(int,input().split())
A = [int(x) for x in input().split()]
F = [int(x) for x in input().split()]
A.sort()
F.sort(reverse=True)
AF =  [A[i]*F[i] for i in range(N)]
maxAF = max(AF)
#二分探索
ans = maxAF
left = 0
right = maxAF
while True:
    mid = (left + right)//2
    dis = 0
    syugyo = 0
    for i in range(N):
        af = AF[i]
        if af > mid:
            dis += af-mid
            amari = (af-mid)%F[i]
            count = (af-mid)//F[i]
            if amari == 0:
                syugyo += count
            else:
                syugyo += count +1
    if syugyo > K:
        if right-mid == 1:
            ans = right
            break
        else:
             left = mid
    else:
        if mid-left == 1:
            ans = mid
            break
        else:
            right = mid
if sum(A) <= K:
    ans = 0
print(ans)

Measured memory_bytes: 119628
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes                \
    cout << "Yes" << endl; \
    return 0;
#define No                \
    cout << "No" << endl; \
    return 0;
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MOD = 1000000007;
typedef long long ll;

template <typename T>
void print(const T &v);

bool is_prime_number(int N)
{
    for (int i = 2; i <= N / 2; i++)
    {
        if (N % i == 0)
            return false;
    }
    return true;
}

int main()
{
    int Q;
    cin >> Q;
    vector<int> l(Q), r(Q);
    rep(i, Q) cin >> l[i] >> r[i];

    vector<int> sums(100000, 0);
    int cnt = 0;
    for (int i = 2; i < 100000; i++)
    {
        if (i % 2 != 0 && is_prime_number(i) && is_prime_number((i + 1) / 2))
        {
            cnt++;
        }
        sums[i] = cnt;
    }
    for (int i = 0; i < Q; i++)
    {
        cout << sums[r[i]] - sums[l[i] - 1] << endl;
    }
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


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

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

  vector<int> X(N);
  rep(i, N) cin >> X[i];

  int ans = INT_MAX;
  int calc = 0;
  for (int i = 1; i <= 100; i++) {
    rep(j, N) calc += (X[j] - i) * (X[j] - i);
    ans = min(ans, calc);
    calc = 0;
  }
  cout << ans << endl;
  return 0;
}

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

const int n=8;
const int Free=1;
const int notFree=-1;

int row[n],col[n],dpos[2*n-1],dneg[2*n-1];
bool X[n][n];

void initialize()
{
	for(int i=0;i<n;i++)row[i]=col[i]=Free;
	for(int i=0;i<2*n-1;i++)dpos[i]=dneg[i]=Free;
	return;
}

void printbord()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(X[i][j]&&row[i]!=j)return;
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cout<<(row[i]==j?"Q":".");
		}
		cout<<endl;
	}
	return;
}

void recursive(int i)
{
	if(i==n){printbord();return;}
	
	for(int j=0;j<n;j++)
	{
		if(col[j]==notFree||dpos[i+j]==notFree||dneg[i-j+n-1]==notFree)continue;
		
		row[i]=j;col[j]=dpos[i+j]=dneg[i-j+n-1]=notFree;
		
		recursive(i+1);
		
		col[j]=dpos[i+j]=dneg[i-j+n-1]=Free;
	}
	return;
}

int main()
{
	initialize();
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)X[i][j]=false;
	
	int k;cin>>k;
	int r,c;
	for(int i=0;i<k;i++)
	{
		cin>>r>>c;
		X[r][c]=true;
	}
	
	recursive(0);
	
	return 0;
}

Measured memory_bytes: 3112
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from itertools import product

def main():
    H, W = LI()
    A = []
    for _ in range(H):
        A.append(LI())
    ans = []
    for y, x in product(range(1, H + 1), range(1, W)):
        j, i = y - 1, x - 1
        if A[j][i] % 2:
            A[j][i + 1] += 1
            ans.append([y, x, y, x + 1])
    x = W
    i = x - 1
    for y in range(1, H):
        j = y - 1
        if A[j][i] % 2:
            A[j + 1][i] += 1
            ans.append([y, x, y + 1, x])
    print(len(ans))
    for arr in ans:
        print(*arr)

    return 0

main()

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

typedef long long ll;
using namespace std;

int main (){
    int n,m;
    cin >> n >> m;
    int k[m];
    bool s[m][n]={};
    int tmp;
    for (int i = 0; i < m; i++){
        cin >> k[i];
        for (int j = 0; j < k[i]; j++){
            cin >> tmp;
            s[i][tmp-1]=true;
        }
    }
    int p[m];
    for (int i = 0; i < m; i++){
        cin >> p[i];
    }

//    cout << "\n";
//    for (int i = 0; i < m; i++){
//        for (int j = 0; j < n; j++){
//            cout << (int)s[i][j] << " ";
//        }
//        cout << "\n";
//    }
//    cout << "\n";

    bool jud;
    int connect;
    int count=0;
    for (int bit = 0; bit < (1<<n); ++bit){
        jud=true;
        for (int i = 0; i < m; i++){
            connect=0;
            for (int j = 0; j < n; j++){
                if(s[i][j] && (bit & (1<<j))) connect++;
            }
            if(connect%2!=p[i]) jud=false;
        }
        if(jud) count++;
    }
    cout << count << "\n";
    return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet};
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::str::*;

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

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

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

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

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

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

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

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

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let cin = stdin();
    let cin = cin.lock();
    let s: String = cin
        .bytes() // Bytes
        .map(|c| c.expect("failed reading char") as char)
        .skip_while(|c| c.is_whitespace()) // c が whitespace である限り skip
        .take_while(|c| !c.is_whitespace()) // c が whitespace でない限り要素を返す
        .collect();
    s.parse().ok().expect("failed parsing")
}

fn main() {
    input! {
        r:isize,
        g:isize,
    }
    println!("{}", r + (g - r) * 2);
}


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

int n,k,x,y,tot,ans;
char ch[2];
int t[2010][1010],f[2010][1010];

int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%s",&x,&y,ch);
		if (ch[0]=='W') x+=k;
		x%=(k<<1); y%=(k<<1);
		if (y>=k)
		{
			y-=k; x+=k;
			x%=(k<<1);
		}
		t[x][y]++;
	}
	
	for (int i=0;i<k;i++)
	{
		for (int j=0;j<k;j++) f[0][i]+=t[j][i];
		for (int j=1;j<k*2;j++) f[j][i]=f[j-1][i]-t[j-1][i]+t[(j+k-1)%(k<<1)][i];
	}
	
	for (int i=0;i<k*2;i++)
	{
		tot=0;
		for (int j=0;j<k;j++) tot+=f[i][j];
		ans=max(ans,tot);
		for (int j=0;j<k;j++)
		{
			tot=tot-f[i][j]+f[(i+k)%(k<<1)][j];
			ans=max(ans,tot);
		}
	}
	printf("%d\n",ans);
	return 0;
}

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

struct Point {
  int x, y;
  Point(int _x, int _y) : x(_x), y(_y) {}
};

struct Vector {
  int x, y;
  Vector(int _x, int _y) : x(_x), y(_y) {};
  Vector(Point f, Point t) : x(t.x - f.x), y(t.y - f.y) {};
  bool clockwise(Vector v){ return x*v.y<y*v.x; }
};

int n;
vector<Point> v,s;

bool sortpoint(const Point& a,const Point& b){
  if(a.y!=b.y)return a.y<b.y;
  return a.x<b.x;
}

bool ok(Point p3){
  if(s.size()<=1)return true;
  Point p1=*(s.rbegin()+1);
  Point p2=*s.rbegin();
  return !Vector(p1,p2).clockwise(Vector(p2,p3));
}

void consider(Point p){
  while(!ok(p))s.pop_back();
  s.push_back(p);
}

void convex_hull() {
  sort(v.begin(),v.end(),sortpoint);
  for(int i=0;i<v.size();++i)consider(v[i]);
  for(int i=v.size()-2;i>=0;--i)consider(v[i]);
  s.pop_back();
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin>>n;
  for(int i=0;i<n;++i){
    int x,y;cin>>x>>y;
    v.push_back(Point(x,y));
  }
  convex_hull();
  cout<<s.size()<<endl;
  for(int i=0;i<s.size();++i){
    cout<<s[i].x<<" "<<s[i].y<<endl;
  }
}

Measured memory_bytes: 4924
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
int main() {
	string s;
	cin >> s;
	vector<int> a(26);
	for (auto p : s) a[p - 'a']++;
	bool ch = 1;
	rep(i, 26) {
		if (a[i] % 2) ch = 0;
	}
	if (ch)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

int n;
vector<int> dat;

void init(int _n){
  n = 1;
  while(n < _n) n *= 2;
  dat.resize(n*2-1,0);
  rep(i,n*2-1){
    dat[i] = 0;
  }
}

void update(int i, int x){
  i += n-1;
  dat[i] += x;
  while(i > 0){
    i = (i-1)/2;
    dat[i] = dat[i*2+1] + dat[i*2+2];
  }
}

int getSum(int x, int y, int k, int l, int r){
  if(r <= x || y <= l) return 0;
  if(x <= l && r <= y) return dat[k];
  else{
    int vl = getSum(x,y,k*2+1,l,(l+r)/2);
    int vr = getSum(x,y,k*2+2,(l+r)/2,r);
    return vl + vr;
  }
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N,q;
  cin >> N >> q;
  init(N);
  rep(i,q){
    //rep(i,2*n-1) cout << dat[i] << ' ';
    //cout << endl;
    int com,x,y;
    cin >> com >> x >> y;
    if(com == 0){
      update(x-1,y);
    }else{
      cout << getSum(x-1,y,0,0,n) << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3904
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



const int MAX = 210;

int N, M;
pint a[MAX];

bool used[MAX];

int main() {
    while (cin >> N >> M) {
        for (int i = 0; i < M; ++i) cin >> a[i].first >> a[i].second;
        
        int it = 1;
        int res = 0;
        bool can = true;
        
        memset(used, 0, sizeof(used));
        while (it <= N) {
            int Max = -1;
            int pMax = -1;
            for (int i = 0; i < M; ++i)
                if (a[i].first <= it && !used[i])
                    if (chmax(Max, a[i].second))
                        pMax = i;
            
            if (pMax == -1) { can = false; break; }
            
            used[pMax] = true;
            it = Max+1;
            ++res;
        }
        
        if (can) cout << res << endl;
        else puts("Impossible");
    }
    
    return 0;
}


Measured memory_bytes: 1160
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s;
vector<string> v;
int main(void){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s;
        v.push_back(s);
    }
    sort(v.begin(),v.end());
    for(string x:v){
        cout<<x;
    }
    cout<<endl;
}


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

int a, b; 

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 	
	cin >> a >> b;

	if (a == 1) {
		a = 14;
	}

	if (b == 1) {
		b = 14;
	}

	if (a > b) {
		cout << "Alice\n";
	}
	else if (b > a) {
		cout << "Bob\n";
	}
	else {
		cout << "Draw\n";
	}
 
	return 0;
}

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

ans = float('inf')
for a in range(1, N // 2 + 1):
    b = N - a

    t = 0
    while a > 0:
        a, r = divmod(a, 10)
        t += r

    while b > 0:
        b, r = divmod(b, 10)
        t += r

    ans = min(t, ans)
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll ;
typedef double db;
const double pi = 3.141592654;
#define pb         push_back
#define forab(i,a,b)       for(int i=(a);i<=(b);i++)
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)
#define pcase(z,x)     printf("Case %ld: %lld\n",z,x)
#define nw	 "\n"
#define mod 1000000007

ll w,e;
int main(void)
{
	CIN;
	ll tc,l,k=0,sum=0,x=0,y,z=0,m=1,n=0,ans=0,cnt=0;
	string s;
	cin>>n;
	ll mx=0;
	map<string,ll>mp;
	while(n--){
		cin>>s;
		mp[s]++;
		mx=max(mx,mp[s]);
	}
	for(auto [a, b] : mp){
		if(b==mx) cout<<a<<nw;
	}
	
}

Measured memory_bytes: 19296
l = list(range(2,10000))

for i in range(len(l)):
    if l[i] == 0:
        continue
    for j in range(i+1,len(l)):
        if l[j] == 0:
            continue
        if l[j] % l[i] == 0:
            l[j] = 0
p = []
for i in l:
    if i==0:
        continue
    p.append(i)

num = int(input())
count = 0
for i in range(num):
    x = int(input())
    isP = True
    for j in p:
        if x == j:
            break
        if x%j == 0:
            isP = False
            break
    if isP:
        count +=1

print(count)



Measured memory_bytes: 5992
fn main() {
    proconio::input! {
        n: usize,
        k: i64,
        a_s: [i64; n],
    }
    let mut counter = vec![0; n + 1];
    let mut first = vec![-1; n + 1];
    let mut current = 1;
    let mut i = 0;
    loop {
        counter[current] += 1;
        if counter[current] == 2 {
            break;
        }
        first[current] = i;
        current = a_s[current - 1] as usize;
        i += 1;
        if i == k {
            println!("{}", current);
            return;
        }
    }
    let loop_num = i - first[current];
    let remain = k - i;
    let remain2 = remain % loop_num;
    for _ in 0..remain2 {
        current = a_s[current - 1] as usize;
    }
    println!("{}", current);
}


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

template <class T, class F = multiplies<T>>
T power(T a, long long n, F op = multiplies<T>(), T e = {1}) {
  assert(n >= 0);
  while (n) {
    if (n & 1) e = op(e, a);
    if (n >>= 1) a = op(a, a);
  }
  return e;
}

template <unsigned M> struct modular {
  using m = modular;
  unsigned v;
  modular(long long a = 0) : v((a %= M) < 0 ? a + M : a) {}
  m operator-() const { return m() -= *this; }
  m& operator+=(m r) { if ((v += r.v) >= M) v -= M; return *this; }
  m& operator-=(m r) { if (v < r.v) v += M; v -= r.v; return *this; }
  m& operator*=(m r) { v = (uint64_t)v * r.v % M; return *this; }
  m& operator/=(m r) { return *this *= power(r, M - 2); }
  friend m operator+(m l, m r) { return l += r; }
  friend m operator-(m l, m r) { return l -= r; }
  friend m operator*(m l, m r) { return l *= r; }
  friend m operator/(m l, m r) { return l /= r; }
  friend bool operator==(m l, m r) { return l.v == r.v; }
  friend string to_string(m a) { return to_string(a.v); }
};

constexpr long long mod = 1e9 + 7;
using mint = modular<mod>;

auto from_left(const string& s) {
  int n = s.size();
  vector<vector<mint>> dp(2, vector<mint>(n + 1));
  dp[0][1] = s[0] != '1';
  dp[1][1] = s[0] != '0';
  for (int i = 1; i < n; i += 2) {
    for (char c : "01"s) {
      for (char d : "01"s) {
        if (s[i] == (c ^ 1) or s[i + 1] == (d ^ 1)) {
          continue;
        }
        if (c == '1' and d == '1') {
          dp[1][i + 2] += dp[0][i];
        } else {
          dp[0][i + 2] += dp[0][i];
        }
      }
    }
  }
  return dp[1];
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  int n = s.size();
  auto dpl = from_left(s);
  auto dpr = from_left({rbegin(s), rend(s)});
  reverse(begin(dpr), end(dpr));
  vector<int> cum(n + 1);
  for (int i = n; i--; ) {
    cum[i] = (s[i] == '?') + cum[i + 1];
  }
  vector<mint> p2(n + 1);
  for (int i = 0; i <= n; ++i) {
    p2[i] = i ? 2 * p2[i - 1] : 1;
  }
  vector<mint> ip2(n + 1);
  for (int i = n; i >= 0; --i) {
    ip2[i] = i < n ? 2 * ip2[i + 1] : 1 / p2[n];
  }
  vector<mint> sum(n + 2);
  for (int r = n - 1; r >= 0; r -= 2) {
    sum[r] = ip2[cum[r]] * dpr[r] + sum[r + 2];
  }
  mint res;
  for (int l = 1; l <= n; l += 2) {
    res += dpl[l] * (dpr[l - 1] + p2[cum[l]] * sum[l + 1]);
  }
  cout << res.v << '\n';
}


Measured memory_bytes: 7856