akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001; // > 10^9
const int MOD = (int)1e9 + 7;
const ll INFLL = 1001001001001001001;  // > 10^18
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

struct UnionFindTree {
    vector<int> parent; //親のところにはブロックサイズの負値が入る
    // 点の数を指定して初期化
    UnionFindTree(int sz) {
        parent.assign(sz, -1);
    }
    // 点xと点yが属する集合を連結する
    bool unite(int x, int y) { //すでに連結ならfalseを返す
        x = find(x); y = find(y); //まず親を見る
        if (x == y) {
            return(false);
        }
        if(parent[x] > parent[y]) { //サイズが大きい方をxにする
            swap(x, y);
        }
        parent[x] += parent[y]; //サイズを足す
        parent[y] = x; //親を指差す
        return(true);
    }
    // 点ｋが属する集合の親
    int find(int k) {
        if(parent[k] < 0) return(k); //親なら自分を返す
        return(parent[k] = find(parent[k])); //親を最新のものに更新しながら返す
    }
    // 点kが属する集合のサイズ
    int size(int k){
        return(-parent[find(k)]);  
    }
};

int main () {
    
    int n,k,l; cin >>n>>k>>l;
    vector<int> p(k); vector<int> q(k);
    rep(i,k) cin >> p[i] >> q[i];
    vector<int> r(l); vector<int> s(l);
    rep(i,l) cin >> r[i] >> s[i];

    UnionFindTree ut1(n);
    for (int i = 0; i < k; i++) {
        int a = p[i], b = q[i]; a--; b--; 
        ut1.unite(a,b);
    }

    UnionFindTree ut2(n);
    for (int i = 0; i < l; i++) {
        int a = r[i], b = s[i]; a--; b--; 
        ut2.unite(a, b);
    }

    vector<P> pairs(n);
    for (int i = 0; i < n; i++) {
        pairs[i] = P(ut1.find(i), ut2.find(i));
    }

    vector<P> same = pairs;
    sort(same.begin(), same.end());

    vector<pair<int, pair<int, int> > > count;
    for (int i = 0; i < n;) {
        int j = i;
        while (j < n && same[i] == same[j]) {
            j++;
        }
        pair<int, P> thisp;
        thisp.first = j - i;
        thisp.second = same[i];
        count.push_back(thisp);
        i = j;
    }

    for (int i = 0; i < n; i++) {
        int ok = -1;
        int ng = count.size();
        while (abs(ok - ng)>1) {
            int m = (ok+ng)/2;
            if (count[m].second <= pairs[i]) {
                ok = m;
            } else {
                ng = m;
            }
        }
        cout << count[ok].first;
        if (i < n-1) {
            cout << " ";
        } 
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 10740
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextInt()
    val count = mutableMapOf<Int,Int>()
    repeat(n) {
        val a = sc.nextInt()
        val get = count.getOrPut(a, {0})
        count[a] = get + 1
    }
    val ans = count.toList().sortedBy { it.second }.take(Math.max(0, count.size - k)).sumBy { it.second }
    println(ans)
}

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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define ALL(v) (v).begin(), (v).end()
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO  cout << "NO"  << endl
#define No  cout << "No"  << endl

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;

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

ll lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

void solve()
{
    ll A, B, C, D; cin >> A >> B >> C >> D;
    A--;
    ll c, d, cd;
    c = (B/C - A/C);
    d = (B/D - A/D);
    ll l = lcm(C, D);
    cd = (B/l - A/l);
    cout << (B-A) - (c+d-cd) << endl;
} 
    
int main() 
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

int main() {
    int n, x, t;
    cin >> n >> x >> t;

    int c = (n + x - 1) / x;
    int ans = c * t;

    cout << ans << endl;


}


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

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << min(a,b)+min(c,d) << endl;
  return 0;
}

Measured memory_bytes: 256
//Induber
//PRAVEEN FULERA

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

typedef long long int ll;
#define mod 1000000007
#define speed ios_base::sync_with_stdio(false);
#define up cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define T int t; cin >> t; while(t--)

vector <int> adj[100005];
bool vis[100005];
map <pair <int , int> , int > dis;
int col[100005];

void dfs(int root){
    vis[root] = true;
    int size = adj[root].size();
    for(int i = 0; i < size; i++){
        if(!vis[adj[root][i]]){
            pair <int , int> p;
            p = mp(root , adj[root][i]);
            if(dis[p]%2==0){
                col[adj[root][i]] = col[root];
            }
            else{
                int cl = (col[root]==1) ? 0 : 1;
                col[adj[root][i]] = cl;
            }
            dfs(adj[root][i]);
        }
    }
}

int main(){
  int n , x, y , w;
  cin >> n;
  for(int i = 0; i < n; i++){
      cin >> x >> y >> w;
      adj[x].pb(y);
      adj[y].pb(x);
      pair <int , int> p1 , p2;
      p1 = mp(x ,y);
      p2 = mp(y , x);
      dis[p1] = w;
      dis[p2] = w;
  }
  col[1] = 0;
  dfs(1);
  for(int i = 1; i <= n; i++){
      cout << col[i] << '\n';
  }
}

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

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep2(i, a, b) for(int i = a; i <= b; ++i)
#define ll long long
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define vi vector<int>

int main() {
	int t;
	ll n, m, a, b;
	cin >> t;
	rep(i, t) {
		cin >> n >> m >> a >> b;
		cout << floor_sum(n, m, a, b) << endl;
	}
	return 0;
}

Measured memory_bytes: 3612
import java.util.*;

public class Main{
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);

      int n=sc.nextInt();
      int m=sc.nextInt();

      int flag = 1;
      int ans = 0;

      int[] a = new int[m];
      for(int i=0;i<m;i++){
        a[i]=sc.nextInt()-1;
      }

      if(m>=2){
      //////////ERROR//////////////////////
      for(int i=0;i<m-1;i++){
        if(a[i+1]==a[i]+1){
          flag = 0;
          break;
        }
      }
      ////////////////////////////////////
      }

      //////////holl record///////////////
      int[] way = new int[n];
      int ccnt=0;
      for(int i=0;i<n;i++){
        for(int j=ccnt;j<m;j++){
          if(i==a[j]){
            way[i] = -1;
            ccnt++;
            break;
          }
        }
      }
      ////////////////////////////////////

      if(n==1){
        way[0] = 1;
      }
      else if(n==2){
        if(a.length==0){
          way[0] = 1;
          way[1] = 2;
        }
        else if(a.length==1){
          way[0] = 0;
          way[1] = 1;
        }
      }
      else if(n>=3){
        if(way[0]!=-1){
          way[0] = 1;
        }
        else{
          way[0] = 0;
        }

        if(way[1]!=-1){
          if(way[0]==0){
            way[1] = 1;
          }
          else if(way[0]==1){
            way[1] = 2;
          }
        }
        else if(way[1]==-1){
          way[1] = 0;
        }

        for(int i=2;i<n;i++){
          if(way[i]!=-1){
            way[i] = way[i-1] + way[i-2];
            way[i] = way[i] % 1000000007;
          }
          else{
            way[i] = 0;
          }
        }
      }

      ans = way[n-1] % 1000000007;

      if(flag==0){
        System.out.println("0");
      }
      else{
        System.out.println(ans);
      }

      for(int i=0;i<n;i++){
        //System.out.println("way["+i+"]="+way[i]);
      }
    }
}


Measured memory_bytes: 48448
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>



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

using namespace std;
int h,w;
string a,b;

int main(){
  cin >> h >> w;
  REP(i,w+2) cout << "#";
  cout << endl;
  REP(i,h){
    cout << "#";
    string s;
    cin >> s;
    cout << s << "#" << endl;
  }
  REP(i,w+2) cout << "#";
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int k; cin >> k;
    VL dis(k, LLINF);
    dis[1] = 1;
    PQ<pair<ll, int>> dik;
    dik.emplace(1, 1);
    while (!dik.empty()) {
        ll d; int now;
        tie(d, now) = dik.top();
        dik.pop();
        if (dis[now] < d)continue;
        if (chmin(dis[(now * 10) % k], d)) {
            dik.emplace(d, (now * 10) % k);
        }
        if (chmin(dis[(now + 1) % k], d + 1)) {
            dik.emplace(d + 1, (now + 1) % k);
        }
    }

    cout << dis[0] << "\n";
}

Measured memory_bytes: 2168
// AOJ 0606: Tower of JOIOI
// 2018.1.10 bal4u@uu

#include <stdio.h>
#include <stdlib.h>

char s[1000005], *p;

int check(char *p, int m)
{
	int i, si, oi, soi, n;

	i = si = oi = soi = n = 0;
	while (*p) {
		if (*p == 'J') {
			if (soi > oi) { oi++; if (++n == m) return 1; }
		} else if (*p == 'O') {
			if (si > i && soi < m) soi++, i++;
		} else {						// *p == 'I'
			if (si < m) si++;
			else if (soi > oi) { oi++; if (++n == m) return 1; }
		}
		p--;
	}
	return 0;
}

int main()
{
	int n, i, oi, ans;
	int lo, hi, m;

	fgets(s+1, 10, stdin), n = atoi(s+1);
	fgets(s+1, 1000005, stdin);
	i = oi = ans = 0;
	p = s+n; while (*p) {
		if (*p == 'J') {
			if (oi) ans++, oi--;
		} else if (*p == 'O') {
			if (i) oi++, i--;
		} else i++;					// *p == 'I'
		p--;
	}
	if (oi > 0) {
		hi = ans + 1 + (i + oi)/2;
		i = 0; while (*++p) {
			if (*p == 'O') break;
			if (*p == 'I') i++;
		}
		lo = ans + i;
		while (lo + 1 < hi) {
			m = (lo + hi) >> 1;
			if (check(s+n, m)) lo = m; else hi = m;
		}
		ans = lo;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 2736
from operator import itemgetter
n = int(input())
data = []
for i in range(n):
    data.append(tuple(map(int,input().split())))

data.sort(key = itemgetter(1))

m = 0

for i, j in data:
    if m+i <= j:
        m += i
    else:
        print("No")
        break
else:
    print("Yes")

Measured memory_bytes: 31840
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll n; cin>>n;
    ll ans=1;
    for(ll i=1;i<=n;i++){
        if(i*i<=n) ans=max(ans,i*i);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3640
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>
#include<math.h>

typedef int32_t i32;
typedef int64_t i64;

#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define ABS(a) ((a) > (0) ? (a) : -(a))

void run (void) {
  i32 n, k;
  scanf ("%" SCNi32 "%" SCNi32, &n, &k);
  printf ("%" PRIi32 "\n", n + 1 - k);
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 128
import scala.io.StdIn.readInt

object Main {

  def find(y:Int):String = {
    var x = y
    while(x>0 && x%10!=3) {
        x = x/10
    }
    if(x%10 == 3) " "+y else ""
  }

  def call(i:Int, n:Int):Unit = {
    var str = ""
    for(i <- 1 to n) {
      if(i%3 == 0){
        print(" "+i)
      } else {
        print(find(i))
      }
    }
    println()
}

  def main(args: Array[String]) = {
    var n = readInt
    call(1,n)
  }

}

Measured memory_bytes: 46920
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int n;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
// vector<int> xl, yl, xr, yr;

// 座標は 2n+2 個ある
void coordinate_compress(vector<int> &xl, vector<int> &xr, int &t) {
  vector<int> xc(2 * n + 2);
  for (int i = 0; i < n; i++) {
    xc[i]     = xl[i];
    xc[i + n] = xr[i];
  }
  xc[2 * n] = 0;
  xc[2 * n + 1] = t;

  sort(xc.begin(), xc.end());
  // 重複を削除
  xc.erase( unique(xc.begin(), xc.end()), xc.end() );

  map<int,int> zip;
  for (int i = 0; i < xc.size(); i++) {
    zip[xc[i]] = i;
  }

  for (int i = 0; i < n; i++) {
    xl[i] = zip[ xl[i] ];
    xr[i] = zip[ xr[i] ];
  }
  t = zip.size() - 1;
}

int main() {
  // ifstream cin("../test.txt");
  while (true) {
    int w,h;
    cin >> w >> h >> n;

    if (!(w|h)) break;

    vector<int> xl, yl, xr, yr;
    xl = vector<int>(n);
    xr = vector<int>(n);
    yl = vector<int>(n);
    yr = vector<int>(n);
    for (int i = 0; i < n; i++) {
      cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];
    }

    // 座標圧縮
    coordinate_compress(xl, xr, w);
    coordinate_compress(yl, yr, h);

    // 10 10
    // 2
    // 5 0 6 10
    // 0 5 10 8
    // ->
    // 3 3
    // 1 0 2 3
    // 1 1 3 2 <- これが実行するたびに違う 0 1 1 0 も。

    // 表示　テープの座標
    // for (int i = 0; i < n; i++) {
    //   cout << w << " " << h << endl;
    //   cout << xl[i] << " " << yl[i] << " " << xr[i] << " " << yr[i] << endl;
    // }

    // テープを貼る
    // 格子は左下の座標を基準にする
    vector< vector<int> > m (w, vector<int>(h+1));
    for (int i = 0; i < w; i++) {
      for (int j = 0; j <= h; j++) {
        m[i][j] = 0;
      }
    }
    for (int i = 0; i < n; i++) {
      for (int x = xl[i]; x < xr[i]; x++) {
        m[x][yl[i]] += 1;
        m[x][yr[i]] -= 1;
        if (xl[i] >= w || xr[i] > w || yl[i] >= h || yr[i] > h)
          cout << "warning" << endl;
      }
    }

    for (int y = 1; y < h; y++) {
      for (int x = 0; x < w; x++) {
        m[x][y] += m[x][y-1];
      }
    }

    // 表示
    // for (int y = h-1; y >= 0; y--) {
    //   for (int x = 0; x < w; x++) {
    //     if (m[x][y] == 0) {
    //       cout << ".";
    //     } else {
    //       cout << "*";
    //     }
    //   }
    //   cout << endl;
    // }

    // 色を幅優先で塗る
    int cnt_clr = 0;
    queue< pair<int, int> > qu;
    for (int x = 0; x < w; x++) {
      for (int y = 0; y < h; y++) {
        if (m[x][y] <= 0) { // テープがなければ色塗り開始
          cnt_clr++;
          qu.push(make_pair(x,y));
          while (!qu.empty()) {
            pair<int, int> p = qu.front();
            qu.pop();
            for (int i = 0; i < 4; i++) {
              int nx = p.first  + dx[i];
              int ny = p.second + dy[i];
              if (nx >= 0 && nx < w && ny >= 0 && ny < h && m[nx][ny] <= 0) {
                m[nx][ny] = 1;
                qu.push(make_pair(nx,ny));
              }
            }
          }
        }
      }
    }

    // 出力
    cout << cnt_clr << endl;
  }
}

Measured memory_bytes: 2396
#include <bits/stdc++.h>
using namespace std;
int main(){

    int N;
    cin >> N;
    vector<pair<int,int> >job(N);
    for (int i = 0; i < N; i++){
        int a, b;
        cin >> a >> b;
        job[i] = make_pair(b, a);
    }
    sort(job.begin(), job.end());

    int time = 0;
    for (int i = 0; i < N; i++){
        time += job[i].second;
        if(time > job[i].first){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 1792
// C - Bridge
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> V;
vector<int> vis;

void dfs(int a, int b, int f){
	if(vis[f]) return;
	vis[f] = 1;
	for(int t:V[f]) if(f!=a || t!=b) dfs(a, b, t);
}

int main(){
	int N, M; cin>>N>>M;
	V.resize(N);
	vis.resize(N);
	vector<pair<int,int>> E;
	for(int i=0; i<M; ++i){
		int a,b; cin>>a>>b; --a, --b;
		E.emplace_back(a, b);
		V[a].push_back(b);
		V[b].push_back(a);
	}
	int ans = 0;
	for(auto [a,b]:E){
		for(auto& x:vis) x = 0;
		dfs(a, b, a);
		if(!vis[b]) ans++;
	}
	cout<< ans <<endl;
}


Measured memory_bytes: 3584
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
ll Baskets[100005];

int main(){

        ll N;
        cin >> N;
        for(int i = 0; i < N; i++){
                ll tmp;
                cin >> tmp;
                Baskets[tmp]++;
        }
        ll result = 0;

        for(int t = 0; t < 100005; t++){
                if(t == 0){
                        if(Baskets[t]+Baskets[t+1] > result){
                                result = Baskets[t]+Baskets[t+1];
                        }
                }
                else if(t == 100000){
                        if(Baskets[t-1]+Baskets[t] > result){
                                result = Baskets[t-1]+Baskets[t];
                        }

                }
                else {
                        if(Baskets[t-1]+Baskets[t]+Baskets[t+1] > result){
                                result = Baskets[t-1]+Baskets[t]+Baskets[t+1];
                        }
                }
        }

        cout << result << endl;

}


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<pli> vpli;
typedef vector<vi> mat;

inline ll read(){
	ll Hashimoto=0,Kanna=1;
	char I_Love=getchar();
	while(I_Love<'0'||I_Love>'9'){
		if(I_Love=='-')Kanna=-1;
		I_Love=getchar();
	}
	while(I_Love>='0'&&I_Love<='9'){
		Hashimoto=Hashimoto*10+I_Love-'0';
		I_Love=getchar();
	}
	return Hashimoto*Kanna;
}

#define I_Love_Hashimoto_Kanna main
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
#define file freopen("I_Love_Hashimoto_Kanna.out","w",stdout);
#define RE cout<<"I_Love_Hashimoto_Kanna"<<endl;
#define Tone(Kanna) cout<<Kanna<<endl;
#define Tall(Hashimoto,Kanna) for(int I_Love=0;I_Love<Kanna;I_Love++)cout<<Hashimoto[I_Love]<<(I_Love==Kanna-1?"\n":" ");
#define FOR(I_Love,Hashimoto,Kanna) for(int I_Love=Hashimoto;I_Love<Kanna;I_Love++)
#define MP(Hashimoto,Kanna) make_pair(Hashimoto,Kanna)
#define REV(Kanna) reverse(Kanna.begin(),Kanna.end());
#define SORT(Kanna) sort(Kanna.begin(),Kanna.end());
#define inf (int)1e9
#define linf (ll)1e15
#define mod (inf+7)

struct edge{
	ll a,b;
	int to;
};

int n,m,s,t;
vector<edge> g[111111];
ll dp1[111111];
ll dp2[111111];

void bfs1(){
	priority_queue<pair<ll,int> >q;
	q.push({linf,s});
	while(!q.empty()){
		ll dis=q.top().first;
		int u=q.top().second;
		q.pop();
		if(dp1[u]>=dis)continue;
		dp1[u]=dis;
		FOR(i,0,g[u].size()){
			int v=g[u][i].to;
			ll nd=dis-g[u][i].a;
			if(dp1[v]>=nd)continue;
			q.push({nd,v});
		}		
	}
}
void bfs2(){
	priority_queue<pair<ll,int> >q;
	q.push({linf,t});
	while(!q.empty()){
		ll dis=q.top().first;
		int u=q.top().second;
		q.pop();
		if(dp2[u]>=dis)continue;
		dp2[u]=dis;
		FOR(i,0,g[u].size()){
			int v=g[u][i].to;
			ll nd=dis-g[u][i].b;
			if(dp2[v]>=nd)continue;
			q.push({nd,v});
		}		
	}
}

int I_Love_Hashimoto_Kanna() {
  fastio;
  n=read();
  m=read();
  s=read();
  t=read();
  s--;
  t--;
  FOR(i,0,m){
  	int u,v,a,b;
  	u=read();
  	v=read();
  	a=read();
  	b=read();
  	u--;v--;
  	edge f;
  	f.a=a;
  	f.b=b;
  	f.to=v;
  	g[u].push_back(f);
  	f.to=u;
  	g[v].push_back(f);
	}
  bfs1();
  bfs2();
  
  vpli ans;
	FOR(i,0,n){
		ans.push_back({linf-(linf-dp1[i])-(linf-dp2[i]),i});
	}
	SORT(ans);
	REV(ans)
	
	int j=0;
	FOR(i,0,n){
		while(ans[j].second<i)j++;
		printf("%lld\n",ans[j].first);
	}
	
	
  
  return 0;
}


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

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

    int A[N];
    rep(i,N) std::cin >> A[i];
    // for(int i=0; i<N; i++){
    //     std::cin >> A[i];
    // }

    std::string S = "YES";
    std::sort(A, A+N);
  
	//rep(i,N) std::cout << A[i] << std::endl;
  	
    rep(i,N-1){
        if(A[i] == A[i+1]){
            S = "NO";
        }
    }

    // for(int i=0; i<N; i++){
    //     for(int j=0; j<N; j++){
    //         if(i != j && A[i] == A[j]){
    //             S = "NO";
    //             break;
    //         }
    //     }
    // }

    std::cout << S << std::endl;

}

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

int main() {
    int const MOD = 1000000007;
    int n;
    string s1, s2;
    cin >> n >> s1 >> s2;

    ll ans = 3;
    rep(i, n) {
        bool back = s1[i - 1] == s2[i - 1];
        if (s1[i] == s2[i]) {
            if (i > 0) ans = (ans * (back ? 2 : 1)) % MOD;
        } else {
            ans = (ans * (back ? 2 : 3)) % MOD;
            i++;
        }
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3624
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner((System.in));
		int n = sc.nextInt();
		int i = sc.nextInt();
		int ans = n - i + 1;

		System.out.println(ans);
		sc.close();
	}
}

Measured memory_bytes: 21972
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        FastReader sc = new FastReader();
        int n = sc.nextInt();
        long curSum = 0L;
        int[] fullArray = new int[100001];
        for (int i = 0; i < n; i++){
            int a = sc.nextInt();
            curSum += a;
            fullArray[a]++;
        }
        int q = sc.nextInt();
        int ci, bi;
        for (int i = 0; i < q; i++){
            ci = sc.nextInt();
            bi = sc.nextInt();
            curSum += (bi-ci)*fullArray[ci];
            fullArray[bi] += fullArray[ci];
            fullArray[ci] = 0;
            System.out.println(curSum);
        }
    }
}
class FastReader{ 
    BufferedReader br; 
    StringTokenizer st; 
    public FastReader() { 
        br = new BufferedReader(new InputStreamReader(System.in)); 
    } 
    String next(){ 
        while (st == null || !st.hasMoreElements()) { 
            try{ 
                st = new StringTokenizer(br.readLine()); 
            }catch (IOException  e){ 
                e.printStackTrace(); 
            } 
        } 
        return st.nextToken(); 
    } 
    int nextInt(){ 
        return Integer.parseInt(next()); 
    } 
    long nextLong(){ 
        return Long.parseLong(next()); 
    } 
    double nextDouble(){ 
      return Double.parseDouble(next()); 
    } 
    String nextLine(){ 
        String str = ""; 
        try{ 
            str = br.readLine(); 
        } 
        catch (IOException e){ 
            e.printStackTrace(); 
        } 
        return str; 
    } 
}


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

int main(){
  int a, p;
  cin >> a >> p;
  cout << (a*3+p)/2 << endl;

  return 0;
}

Measured memory_bytes: 3636
import sys


N, A, B, C, D = map(int, input().split())

S = {i : s for i, s in enumerate(input(), 1)}

# AとBは接触しないので個別に進めればOK
if C < D:
  while B != D:
    if S[B+1] == '.':
      B += 1
    else:
      if S[B+2] == '.':
        B += 2
      else:
        print("No")
        sys.exit()

  while A != C:
    if S[A+1] == '.':
      A += 1
    else:
      if S[A+2] == '.':
        A += 2
      else:
        print("No")
        sys.exit()
  print("Yes")
  
# AとBは途中ですれ違う必要がある
# BをAが飛び越えられる場所(3マス連続で空白になる場所)で止めておくことにする
# Aのループは普通に回してよい なぜならば、3マス連続の空白は普通に通過できるし、
# その間Bがそこにいることにすれば良いため
else:
  # AがBを追い越せる場所があるか判定をしつつBをゴールまで移動させる
  stay_B = False
  if S[B-1] == '.':
    continuous_empty = 2
  else:
    continuous_empty = 1

  while B != D:
    if S[B+1] == '.':
      B += 1
      continuous_empty += 1
      if continuous_empty == 3:
        stay_B = True
    else:
      if S[B+2] == '.':
        B += 2
        continuous_empty = 1
      else:
        print("No")
        sys.exit()
   
  # Bが到達できる場合
  if stay_B or (continuous_empty == 2 and S[D+1] == '.'):
    while A != C:
      if S[A+1] == '.':
        A += 1
      else:
        if S[A+2] == '.':
          A += 2
        else:
          print("No")
          sys.exit()
    print("Yes")
      
  # Bが空白地帯に到達できなければNo
  else:
    print("No")

Measured memory_bytes: 27488
def combi(n)
	ans = 0
	10.times{|i|
		10.times{|j|
			10.times{|k|
				10.times{|l|
					ans += 1 if i + j + k + l == n
				}
			}
		}
	}
	ans
end

while n = gets
	puts combi(n.to_i)
end

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

int main() {
  int n; cin >> n;
  string a, b, c; cin >> a >> b >> c;
  int ans = 0;
  for(int i = 0; i < n; i++) {
    set<char> st;
    st.insert(a[i]);
    st.insert(b[i]);
    st.insert(c[i]);
    ans += st.size() - 1;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
import java.awt.Label;
import java.util.*;
public class Main{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        while(true)
        {
            int n = sc.nextInt();
            int r = sc.nextInt();
            if(n == 0 && r == 0) break;
            int[] v = new int [n];
            for (int i = 0; i < n; i++) {
               v[i] = i+1; 
            }
            for (int i = 0; i < r; i++) {
                int p = sc.nextInt();
                int c = sc.nextInt();
                int[] bufp = new int[p];
                int[] bufc = new int[c];
                for (int j = 0; j < p-1; j++) {
                    bufp[j] = v[j+n-p+1]; 
                }
                for (int j = 0; j < c; j++) {
                    bufc[j] = v[n-p-c+1+j];
                }
                for (int j = 0; j < c; j++) {
                    v[j+n-c] = bufc[j];
                }
                for (int j = 0; j < p-1; j++) {
                    v[n-c-p+1+j] = bufp[j]; 
                }
            }
            System.out.println(v[n-1]);


        }

        sc.close();
    }
    
    public static void printary(int[] a)
    {
        for ( int i = 0; i < a.length; i++) {
            if(i>0) System.out.print(" ");
            System.out.print(a[i]);
        }
        System.out.println();
    }
}


Measured memory_bytes: 38072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

int main(){
    int n;
    cin >> n;
    int tmp=0, ans=0;
    rep(i, n){
        int h; cin >> h;
        if(h-tmp <0) ans += tmp-h;
        tmp = h; 
    }
    ans += tmp;
    cout << ans << endl;
    // printf("%d\n", N);
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;


const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

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;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()

int main(){
    int A,B,X;
    cin>>A>>B>>X;
    if(A<=X&&A+B>=X){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

//a=97,z=122



Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    map<int,int> r,g,b;
    int A,B;
    ll ans=0;
    int n; cin>>n;
    char ch;
    rep(i,n){
        cin>>ch; 
        if(ch=='R') r[i]=1;
        if(ch=='G') g[i]=1;
        if(ch=='B') b[i]=1;
    }
    int bs=b.size();
    for(auto p : r){
        for(auto q : g){
            A=p.first; B=q.first;
            ans+=bs;
            if(b.count(2*A-B)) ans--;
            if(b.count(2*B-A)) ans--;
            if((A+B)%2==0){
                if(b.count((A+B)/2)) ans--;
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3760
#include <assert.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;

# define INF 0x3f3f3f3f

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define DEBUG(vec) for (auto v : vec) { cout << v << " "; } cout << endl;

using namespace std;

int A[100010] = {};

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

  int N, K;
  cin >> N >> K;
  REP(i, N) {
    cin >> A[i];
  }
  cout << (N - 1 + K - 2) / (K - 1) << endl;
  return 0;
}


Measured memory_bytes: 640
// Math = ♥️

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define ld long double
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pq priority_queue
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define sz(c) ((ll)c.size())
#define ordered_set                            \
    tree<ll, null_type, less<ll>, rb_tree_tag, \
         tree_order_statistics_node_update>

struct SegmentTree {
    vi st;

    SegmentTree(ll n) {
        st.resize(4 * n, LLONG_MIN);
    }

    ll query(ll l, ll r, ll left, ll right, ll vertex = 1) {
        if (l > r) {
            return LLONG_MIN;
        }

        if (l == left && r == right) {
            return st[vertex];
        }

        ll mid = (left + right) / 2;
        return max(query(l, min(r, mid), left, mid, vertex * 2),
                   query(max(mid + 1, l), r, mid + 1, right, vertex * 2 + 1));
    }

    void update(ll ind, ll val, ll left, ll right, ll vertex = 1) {
        if (left == right) {
            st[vertex] = max(st[vertex], val);
            return;
        }

        ll mid = (left + right) / 2;
        if (ind <= mid) {
            update(ind, val, left, mid, vertex * 2);
        } else {
            update(ind, val, mid + 1, right, vertex * 2 + 1);
        }

        st[vertex] = max(st[vertex * 2], st[vertex * 2 + 1]);
    }
};

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

    ll n;
    cin >> n;

    vi h(n), b(n);

    for (auto &it : h) {
        cin >> it;
    }

    for (auto &it : b) {
        cin >> it;
    }

    map<ll, ll> ms;
    for (auto it : h) {
        ms[it];
    }

    ll curr = 0;
    for (auto &it : ms) {
        it.ss = curr;
        curr++;
    }

    for (auto &it : h) {
        it = ms[it];
    }

    curr++;
    SegmentTree s(curr);
    ll dp[n];

    for (int i = n - 1; i >= 0; i--) {
        auto up = s.query(h[i] + 1, curr - 1, 0, curr - 1);

        dp[i] = b[i];
        if (up != LLONG_MIN) {
            dp[i] += up;
        }
        s.update(h[i], dp[i], 0, n - 1);
    }

    ll maxi = 0;
    for (auto it : dp) {
        maxi = max(it, maxi);
    }

    cout << maxi << "\n";
}


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

using namespace std;

bool hanttei(pair<int, int> k, pair<int, int> s) {
    if(k.second != s.second){
        return k.second < s.second;
    }else{
        return k.first < s.first;
    }
}

int main(){
  int n;
  bool ans=true;
  int64_t time=0;
  int64_t need=0;
  cin >> n;
  vector< pair<int, int> > work;
  for(int i=0;i<n;i++){
    int a=0;
    int b=0;
    cin >> a >> b;
    work.push_back( make_pair(a, b) );
  }
  sort(work.begin(), work.end(), hanttei );
  // cout << endl;
  // for(auto a: work){
  //   cout << a.first << " " << a.second << endl;
  // }
  // cout << endl;
  for(int i=0;i<n;i++){
    need = need+work.at(i).first;
    time = work.at(i).second;
    // cout << need << " " << time << endl;
    if(need>time){
      ans=false;
      break;
    }
  }

  if(ans){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 2420
#include<bits/stdc++.h>
#define ll long long int
#define pii pair<int,pair<int,int>>
#define F first
#define S second
using namespace std;
#define mod 1000000007

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

    int x; cin>> x;
    if(x%2==0 || x%5==0) {cout<<-1<<endl; return 0;}
    ll curr=7; ll cnt=1;
    while(curr%x){
        curr=(curr*10+7)%x;
        cnt++;
    }
    cout<< cnt<<endl;

}


Measured memory_bytes: 3644
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <queue>
#include <cctype>
#include <climits>
#include <stack>
using namespace std;
 
int n,m,r;
const int INF=1e7;
int d[2][200][200],z[1000];
typedef pair<int,int> P;
 
int main(){
 
 
    while(scanf("%d %d",&n,&m),n){
	    
	   for(int i=0;i<n;i++){
		  for(int j=0;j<n;j++) d[0][i][j]=d[1][i][j]=INF;
		  d[0][i][i]=d[1][i][i]=0;
	   }
	    
	   for(int i=0;i<m;i++){
		  int x,y,t;
		  char c;
		  scanf("%d %d %d %c",&x,&y,&t,&c);
		  x--; y--;
		  
		  d[c=='L'][x][y]=min(d[c=='L'][x][y],t);
		  d[c=='L'][y][x]=min(d[c=='L'][y][x],t);
	   }
	    
	   for(int k=0;k<n;k++){
		  for(int i=0;i<n;i++){
			 for(int j=0;j<n;j++){
				d[0][i][j]=min(d[0][i][j],d[0][i][k]+d[0][k][j]);
				d[1][i][j]=min(d[1][i][j],d[1][i][k]+d[1][k][j]);
			 }
		  }
	   }
	    
	   scanf("%d",&r);
	   for(int i=0;i<r;i++){
		  scanf("%d",&z[i]);
		  z[i]--;
	   }
	    
	   vector<vector<int> > dp(1000,vector<int>(200,INF));
	   dp[0][z[0]]=0;
 
	   int res=INF;
	   for(int i=1;i<r;i++){
		  for(int j=0;j<n;j++){
						    
			 for(int k=0;k<n;k++){
				dp[i][k]=min(dp[i][k],dp[i-1][j]+d[1][z[i-1]][j]+d[0][j][k]+d[1][k][z[i]]);
				if(i==r-1 && res>dp[i][k]) res=dp[i][k];
			 }
			 dp[i][j]=min(dp[i][j],dp[i-1][j]+d[1][z[i-1]][z[i]]);
			 if(i==r-1 && res>dp[i][j]) res=dp[i][j];
		  }
	   }
 
	   printf("%d\n",res);
	    
    }
}

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

int main() {
  ll int a, b;
  string op;
  cin >> a >> op >> b;
  if(op=="-") cout << a-b << endl;
  else cout << a+b << endl;
  
  
  return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e9 + 7;
const int iinf = 1 << 28;
const long long llinf = 1ll << 60;
const double PI = 3.14159265;

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

void work() {
    int k; cin>>k;
    ll ans = 0;
    for (int a = 1; a <= k; ++a) {
        for (int b = 1; b <= k; ++b) {
            ll g = gcd(a,b);
            for (int c = 1; c <= k; ++c) {
                ans += gcd(g, c);
            }
        }
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //int nt; cin>>nt; while (nt--) work();
    work();
    return 0;
}


Measured memory_bytes: 3656
#include <iostream>

using namespace std;

int table[10][10];

bool check(int a, int b, int c, int d, int e) {
	return table[table[table[table[table[0][a]][b]][c]][d]][e] == 0;
}

int main() {
	for (int i = 0; i < 10; ++i)
		for (int j = 0; j < 10; ++j)
			cin >> table[i][j];
	int ans = 0;
	for (int a = 0; a < 10; ++a) {
		for (int b = 0; b < 10; ++b) {
			for (int c = 0; c < 10; ++c) {
				for (int d = 0; d < 10; ++d) {
					bool flag = false;
					int e = table[table[table[table[0][a]][b]][c]][d];
					for (int i = 0; i < 10; ++i) {
						if (a != i) if (check(i, b, c, d, e)) flag = true;
						if (b != i) if (check(a, i, c, d, e)) flag = true;
						if (c != i) if (check(a, b, i, d, e)) flag = true;
						if (d != i) if (check(a, b, c, i, e)) flag = true;
						if (e != i) if (check(a, b, c, d, i)) flag = true;
					}
					if (a != b) if (check(b, a, c, d, e)) flag = true;
					if (b != c) if (check(a, c, b, d, e)) flag = true;
					if (c != d) if (check(a, b, d, c, e)) flag = true;
					if (d != e) if (check(a, b, c, e, d)) flag = true;
					if (flag) ans++;
				}
			}
		}
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3096
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iomanip>


int main(){
  long long int N;
  scanf("%lld", &N);
  
  if(N%2 == 0){
    std::cout << 0.5 << std::endl;
  }
  else{
    std::cout << std::setprecision(15) << (N/2+1)/(N*1.0);
  }
  
  return 0;
}


Measured memory_bytes: 764
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#define M 155
#define INF 100000000000LL
using namespace std;
long long dp[M][M];
int S[M],R[M];
int main(){
    int n,a,b;
    while(scanf("%d%d%d",&n,&a,&b)!=EOF){
        int j,k,i;
        for(j=1;j<=n;j++){
            scanf("%d%d",&R[j],&S[j]);   
        }
        for(j=0;j<=M-5;j++){
            for(k=0;k<=M-5;k++){
                dp[j][k]=INF;
            }
        }
        for(j=0;j<=S[n];j++) dp[n][j]=-INF;
        long long sum=S[n];
        for(j=n-1;j>=1;j--){
            sum+=S[j];
            for(k=sum;k>=S[j];k--){
                dp[j][k]=-INF;
                for(i=sum-k+1;i<=sum;i++){
                    dp[j][k]=max(-dp[j+1][i]-R[j]+1,dp[j][k]);
                }
                //if(j==2&&k==10) printf("dp = %d\n",dp[j][k]);
                long long t=INF;
                for(i=k;i<=sum;i++){
                    t=min(dp[j+1][i]+1+R[j],1LL*t);
                }
                //if(j==1&&k==10) printf("t = %d\n",t);
                dp[j][k]=min(dp[j][k],max(1LL*t,1LL));
            }
        }
        int ans=0;
        //printf("dp = %d\n",dp[1][119]);
        //printf("%d\n",dp[1][7]);
        for(j=0;j<=sum;j++){
            if(dp[1][j]<=a-b) ans=max(ans,j);
        }
        printf("%d %d\n",ans,sum-ans);
    }
    //system("pause");
    return 0;
}

Measured memory_bytes: 1376
#include <bits/stdc++.h>
        using namespace std;
        #define tani_nachi_ke  ios_base::sync_with_stdio(false); cin.tie(NULL);
        #define M_PI 3.14159265358979323846
        #define data data_
        #define ff first
        #define ss second
        #define pb push_back
        #define ld long double
        #define int long long
        #define print(t) cout << "Case #" << t << ": ";
        int32_t main()
        {
            tani_nachi_ke  
            
            int n,m,x;
            cin >> n >> m >> x;
            int c[n], a[n][m];
            for(int i = 0; i < n; i++)
            {
                cin >> c[i];
                for(int j = 0; j < m; j++)
                    cin >> a[i][j];
            }
            int ans = 1e18;
            for(int i = 0; i < (1 << n); i++)
            {
                int cur = 0;
                int b[m] = {0};
                for(int j = 0; j < n; j++)
                {
                    if(i&(1<<j))
                    {
                        for(int t = 0; t < m; t++)
                            b[t] += a[j][t];
                        cur += c[j];
                    }
                }
                bool ok = 1;
                // cout << cur << endl;
                for(int t = 0; t < m; t++)
                    if(b[t] < x)
                        ok = 0;
                if(ok)
                    ans = min(ans, cur);

            }
            if(ans != 1e18)
                cout << ans << endl;
            else 
                cout << -1 << endl;
           return 0;
        }
          

Measured memory_bytes: 3652
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>

#define pb push_back
#define mp make_pair

using namespace std;

template<typename T>inline void upmin(T &x,T y) { y<x?x=y:0; }
template<typename T>inline void upmax(T &x,T y) { x<y?x=y:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1e18;

const int N=1e6+100;

int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

VI e[N];
int l,r,mid,f[N],n;
inline void dfs(int k) {
	for (int t:e[k]) {
		e[t].erase(find(e[t].begin(),e[t].end(),k));
		dfs(t);
	}
}
inline bool solve(int k) {
	int m=e[k].size(),i,L,R,MID;VI w(m);
	for (i=0;i<m;i++) {
		if (!solve(e[k][i])) return false;
		w[i]=f[e[k][i]]+1;
	}
	if (~m&1) w.pb(0),m++;
	sort(w.begin(),w.end());
	L=0,R=m;
	while (L!=R) {
		MID=(L+R)>>1;
		f[k]=w[MID];
		w.erase(w.begin()+MID);
		for (i=0;i<m/2;i++)
			if (w[i]+w[m-2-i]>mid) break;
		w.insert(w.begin()+MID,f[k]);
		if (i==m/2) R=MID;
		else L=MID+1;
	}
	if (L==m) return false;
	f[k]=w[L];
	return true;
}
int main()
{
	int n=gi(),i,a,b,ans=0,rt;
	for (i=1;i<n;i++) {
		a=gi(),b=gi();
		e[a].pb(b),e[b].pb(a);
	}
	for (i=1;i<=n;i++) ans+=e[i].size()&1,e[i].size()==1?rt=i:0;
	dfs(rt);
	l=1,r=n;
	while (l!=r) {
		mid=(l+r)>>1;
		if (solve(rt)&&f[e[rt][0]]<mid) r=mid;
		else l=mid+1;
	}
	cout<<ans/2<<" "<<l<<endl;
	return 0;
}


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

int n;
char s[100010];

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    if (s[n] == '1' || s[1] == '0') { puts("-1"); return 0; }
    for (int i = 1; i < n; i++)
        if (s[i] != s[n - i])
        {
            puts("-1");
            return 0;
        }
    int sz = n - 1, now = 1, nn = 1;
    for (int i = n >> 1; i > 0; i--)
        if (s[i] == '1')
        {
            for (int j = 0; j < sz - i; j++)
                printf("%d %d\n", now, ++nn);
            printf("%d %d\n", now, ++nn);
            sz = i - 1;
            now = nn;
        }
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
int main(void){
    int a,b;
    cin>>a>>b;
    a%=500;
    cout<<(a>b?"No":"Yes");
    return 0;
}

Measured memory_bytes: 256
A,B,C,X,Y=map(int,input().split())
Z = min(X, Y)
price1 = min((A+B)*Z, 2*C*Z)
if X > Y:
    price2 = min((X-Y)*A, 2*(X-Y)*C)
elif X < Y:
    price2 = min((Y-X)*B, 2*(Y-X)*C)
else:
    price2 = 0
print(price1 + price2)

Measured memory_bytes: 61900