akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _0013
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> numberList = new List<string>();
            List<string> departureList = new List<string>();
            string str = "";
            while ((str = Console.ReadLine()) != null)
            {
                if (str == "0")
                {
                    departureList.Add(numberList[numberList.Count - 1]);
                    numberList.RemoveAt(numberList.Count - 1);
                }
                else
                {
                    numberList.Add(str);
                }
            }
            foreach (var item in departureList)
            {
                Console.WriteLine(item);
            }
        }
    }
}



Measured memory_bytes: 15792
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pii pair<ll,ll>
#define vi vector<ll>
#define vii vector<pii>
#define mi map<ll,ll>
#define mii map<pii,ll>
#define ms map<string,ll>
#define itr ::iterator
#define all(x) x.begin(),x.end()
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fe(i,a,b) for(ll i=a;i<=b;i++)
#define fn(i,a,b) for(ll i=a;i>b;i--)
#define fm(it,m) for(it = m.begin();it != m.end();++it)
#define db(i) cout<<i<<"  "
#define M 1000000007
 
int main()
{ ll t=1;
  //cin>>t;
  while(t--)
  { ll h=0,a=0,k=0;
    cin>>h>>a;
    if(h%a==0)
        cout<<h/a;
    else cout<<(h/a)+1;
 
  }
return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
  private static int solve(int n, int[] as) {
    Set<Integer> set = new HashSet<>();
    for (int a : as) {
      if (set.contains(a)) {
        set.remove(a);
      } else {
        set.add(a);
      }
    }
    return set.size();
  }
  
  private static void execute(ContestReader reader, PrintWriter out) {
    int n = reader.nextInt();
    int[] as = reader.nextInt(n);
    out.println(solve(n, as));
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;
  
  ContestReader(InputStream in) {
    reader = new BufferedReader(new InputStreamReader(in));
  }
  
  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }
  
  public int nextInt() {
    return Integer.parseInt(next());
  }
  
  public long nextLong() {
    return Long.parseLong(next());
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}


Measured memory_bytes: 44188
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <map>
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(int i = (a); i > (b); --i)
#define SZ(a) a.size()
#define ll long long
#define ull unsigned long long
using namespace std;

int main() {

	ll N;
	cin >> N;
	ll A[110];
	FOR(i, 0, N) {
		cin >> A[i];
	}

	ll min = 1000000010;
	ll max = 0;

	FOR(i, 0, N) {
		if (min > A[i])
			min = A[i];
		if (max < A[i])
			max = A[i];
	}
	cout << abs(min - max) << endl;


	system("pause");
	return 0;
}

Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
//const long long MOD = ;
const long long INF_LL = 1e18+3; const int INF_int = 1e9+3;
#define ll long long
#define rep(i,n) for(int i = 0;i<n;i++)
#define lrep(i,n) for(long long i = 0;i<n;i++)
#define All(a) a.begin(),a.end()
#define Debug_Output_ALL(a) for(auto itr = a.begin();itr!=a.end();itr++) cout << *itr << " ";cout << endl;
#define pll pair<ll,ll>
int main(){
    int n;
    cin >> n;
    vector<pll> a(n);
    vector<pll> b(n);
    rep(i,n) cin >> a[i].first >> a[i].second;
    rep(i,n) b[i].first = a[i].second,b[i].second = a[i].first;
    sort(All(a));
    sort(All(b));
    long double max_e,min_e;
    if(n%2==1){
        min_e = a[(n-1)/2].first;
        max_e = b[(n-1)/2].first;
    }
    else{
        min_e = (double(a[(n-2)/2].first+a[(n)/2].first))/2.0;
        max_e = (double(b[(n-2)/2].first+b[(n)/2].first))/2.0;     
    }
    //cout << min_e << " " << max_e << endl;
    /*ll ans = 0;
    rep(i,n){
        ans+=(min(a[i].second,max_e)-max(a[i].first,min_e)+1);
    }*/
    ll ans;
    if(n%2==1){
        ans=max_e-min_e+1;
    }
    else{
        ans = (max_e-min_e)*2+1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 9592
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;

//typedef modint998244353 mint;

const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;

const ll MAX = 1e9 + 5;


int main() {
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	s--;
	t--;
	vector<vector<pll>> g1(n);
	vector<vector<pll>> g2(n);
	for (int i = 0; i < m; i++) {
		ll u, v, a, b;
		cin >> u >> v >> a >> b;
		u--;
		v--;
		g1[u].emplace_back(make_pair(v, a));
		g1[v].emplace_back(make_pair(u, a));
		g2[u].emplace_back(make_pair(v, b));
		g2[v].emplace_back(make_pair(u, b));
	}

	vector<ll> d1(n, INF);
	vector<ll> d2(n, INF);

	d1[s] = 0;
	d2[t] = 0;
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	vector<bool> ic1(n);
	pq.push(make_pair(0, s));
	while (!pq.empty()) {
		int v = pq.top().second;
		pq.pop();
		if (ic1[v]) {
			continue;
		}
		
		for (pii e : g1[v]) {
			int u = e.first;
			int c = e.second;

			if (d1[u] > d1[v] + c) {
				d1[u] = d1[v] + c;
				pq.push(make_pair(d1[u], u));
			}
		}

		ic1[v] = true;
	}

	vector<bool> ic2(n);
	pq.push(make_pair(0, t));
	while (!pq.empty()) {
		int v = pq.top().second;
		pq.pop();
		if (ic2[v]) {
			continue;
		}

		for (pii e : g2[v]) {
			int u = e.first;
			int c = e.second;

			if (d2[u] > d2[v] + c) {
				d2[u] = d2[v] + c;
				pq.push(make_pair(d2[u], u));
			}
		}

		ic2[v] = true;
	}

	vector<ll> ans(n);
	ll a = 0;
	for (int i = n - 1; i >= 0; i--) {

		a = max(a,(ll) 1e15 - (d1[i] + d2[i]));
		ans[i] = a;
	}

	for (ll ai : ans) {
		cout << ai << endl;
	}
}

Measured memory_bytes: 20940
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;

int main() {
#ifdef LOCAL_EXEC
//	freopen("sample.in", "r", stdin);
//	freopen("sample.out", "w", stdout);
#else
  ios_base::sync_with_stdio(false); cin.tie(NULL);
#endif

  ll n, p; cin >> n >> p;
  ll pp = p;
  ll ans = 1;
  for (ll i = 2; i <= pp && i <= 10000001; i++) {
    if (pp % i == 0) {
      int f = 0;
      while (pp % i == 0) {
        pp /= i;
        f++;
      }
      f /= n;
      while (f > 0) {
        f--;
        ans *= i;
      }
    }
  }
  if (pp > 1 && n == 1) ans *= pp;
  cout << ans << endl;

  return 0;
}


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

// Segment tree. Assignment on interval, single element access.
template<typename T>
class SegTree{
    size_t n;
    int h;
    vector<T> data;
    vector<bool> used;
    static T combine(T L, T R){
        return max(L, R);
    }
    void apply(size_t i, T v){
        data[i] = v;
        used[i] = true;
    }
    void push(size_t p){       // propagates the changes from the root to node p.
        for (int s = h; s > 0; --s){
            size_t i = p >> s;
            if (used[i]){
                apply(i*2, data[i]);
                apply(i*2+1, data[i]);
                used[i] = false;
            }
        }
    }
    int calc_h(size_t nn){
        int hh = 1;
        for (; nn > 1; ++hh, nn >>= 1);
        return hh;
    }

public:
    SegTree(size_t _n): n(_n), h(calc_h(n)), data(vector<T>(2 * n, numeric_limits<int>::max())), used(vector<bool>(2 * n, false)){used[1] = true;}
    SegTree(const vector<T> &src): n(src.size()), h(calc_h(n)), data(vector<T>(2 * n, 0)), used(vector<bool>(2 * n, false)){init(src);}
    void init(const vector<T> &src) {for (size_t i = 0; i != n; ++i) apply(n + i, src[i]);}
    void modify(size_t L, size_t R, T v){  // assign v to range [L, R)
        L += n;
        R += n;
        push(L);
        push(R - 1);
        for (; L < R; L >>= 1, R >>= 1){
            if (L & 1) apply(L++, v);
            if (R & 1) apply(--R, v);
        }
    }
    T query(size_t i){
        push(i + n);
        return data[i + n];
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    SegTree<int> seg(n);
    while (q--){
        int c;
        cin >> c;
        if (c == 0){
            int s, t, x;
            cin >> s >> t >> x;
            seg.modify(s, t + 1, x);
        }
        else{
            int i;
            cin >> i;
            cout << seg.query(i) << '\n';
        }
    }
    return 0;
}

Measured memory_bytes: 3884
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=200000+10;
const int maxm=100000+10;
const int mod=(int)1e9+7;
const int INF=0x3f3f3f3f;
const ll LINF=(1LL<<62);
const double eps=1e-8;
const double PI=acos(-1.0);
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for (int i=(a);i<b;i++)
#define ALL(x) x.begin(),x.end()
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define X first
#define Y second
int main(){
#ifdef local
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
#endif
    //ios::sync_with_stdio(false); cin.tie(0);
    ll x,y; scanf("%lld%lld",&x,&y);
    int ans=0;
    ll cur=x;
    while (cur<=y){
        ans++;
        cur*=2;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

vector<int> G[100001];
int N;
int root;
int MAX_LOG_V = 17;
int POW[18];

int** parent;
int* depth;

void dfs(int node_id,int parent_id,int d){
	parent[0][node_id] = parent_id;
	depth[node_id] = d;
	for(int i = 0; i < G[node_id].size(); i++){
		if(G[node_id][i] != parent_id)dfs(G[node_id][i],node_id,d+1);
	}
}

//?????????
void init(){

	dfs(root,-1,0);

	for(int k = 0; k + 1 < MAX_LOG_V; k++){
		for(int node_id = 0; node_id < N; node_id++){
			if(parent[k][node_id] < 0)parent[k+1][node_id] = -1;
			else{
				parent[k+1][node_id] = parent[k][parent[k][node_id]];
			}
		}
	}
}


int lca(int left,int right){

	if(depth[left] > depth[right])swap(left,right);

	for(int k = MAX_LOG_V-1; k >= 0; k--){
		if(depth[right]-depth[left] >= POW[k]){
			right = parent[k][right];
		}
	}

	if(left == right)return left;

	for(int k = MAX_LOG_V-1; k >= 0; k--){
		if(parent[k][left] == parent[k][right]){
			//Do nothing
		}else{
			left = parent[k][left];
			right = parent[k][right];
		}
	}
	return parent[0][left];
}



int main(){

	for(int i = 0; i <= 17; i++)POW[i] = pow(2,i);

	scanf("%d",&N);

	int num,child;

	for(int i = 0; i < N; i++){
		scanf("%d",&num);
		for(int k = 0; k < num; k++){
			scanf("%d",&child);
			G[i].push_back(child);
		}
	}

	parent = new int*[MAX_LOG_V];
	for(int i = 0; i < MAX_LOG_V;i++)parent[i] = new int[N];
	depth = new int[N];
	root = 0;
	init();

	int Q;
	scanf("%d",&Q);

	int left,right;

	for(int i = 0; i < Q; i++){
		scanf("%d %d",&left,&right);
		printf("%d\n",lca(left,right));
	}

	return 0;
}

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

void Main()
{
    int a, b, c, k; // 赤、緑、青
    cin >> a >> b >> c >> k;
    int n = 0;
    while(b <= a){
        b *= 2;
        n++;
    }
    while(c <= b){
        c *= 2;
        n++;
    }
    if(k >= n) cout << "Yes" << endl;
    else cout << "No" << endl;

    // a < b < c
}

int main(int argc, char **argv)
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    Main();
    return 0;
}


Measured memory_bytes: 3644
ans = []

loop do

  grid = ""

  8.times{ grid += gets.chomp }

  case grid
  when /^0*110{6}110*$/
    ans << 'A'
  when /^0*10{7}10{7}10{7}10*$/
    ans << 'B'
  when /^0*1{4}0*$/
    ans << 'C'
  when /^0*10{6}110{6}10*$/
    ans << 'D'
  when /^0*110{7}110*$/
    ans << 'E'
  when /^0*10{7}110{7}10*$/
    ans << 'F'
  when /^0*110{5}110*$/
    ans << 'G'
  end

  unless gets
    break
  end

end

ans.each{ |a| puts a }



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

/************* Using *************/
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using graph_t = vector<vector<ll>>;

/*********** Constants ***********/
const auto INF  = static_cast<int>(1e10);
const auto INFL = static_cast<ll>(1e18);
const auto MOD  = static_cast<ll>(1e9 + 7);
const auto NIL  = nullptr;

/*********** Variables ***********/
ll N, M;
vector<ll> A, B;

/************* Utils *************/

/*********** Functions ***********/
bool init() {
    cin >> N; A.resize(N + 1, 0); B.resize(N + 1, 0);
    for (ll i = 1; i <= N; i++) {
        cin >> A[i];
    }
    return true;
}

void solve() {
    for (ll i = N; i > 0; i--) {
        ll tmp = 0;
        for (ll j = i * 2; j <= N; j += i) {
            tmp += B[j];
        }
        if (A[i] == 1 && tmp % 2 == 0) {
            B[i] = 1;
        }
        else if (A[i] == 0 && tmp % 2 == 1) {
            B[i] = 1;
        }
    }
}

void output() {
    M = count(B.begin(), B.end(), 1);
    cout << M << endl;
    if (M > 0) {
        bool first = true;
        for (ll i = 1; i <= N; i++) {
            if (B[i] == 0) {
                continue;
            }
            if (first) {
                cout << i;
                first = false;
            }
            else {
                cout << " " << i;
            }
        }
        cout << endl;
    }
}

int main() {
    init();
    solve();
    output();
    return 0;
}


Measured memory_bytes: 3968
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <cstdint>
#include <iostream>
#include <string>

constexpr int64_t kMaxNumberOfTowns = 200000;

void CallTeleporter(std::istream &input_stream) noexcept;

class Teleporter {
 public:
  Teleporter() noexcept;
  ~Teleporter() noexcept;
  void SetNumberOfTowns(const int64_t number_of_towns) noexcept;
  void SetMapping(const int64_t from, const int64_t to) noexcept;
  int64_t SearchFinalTown(const int64_t start_town, const int64_t number_of_teleportations) noexcept;

 private:
  int64_t number_of_towns_;
  int64_t ported_to_[kMaxNumberOfTowns + 1];
  int64_t visited_time_[kMaxNumberOfTowns + 1];
};

void CallTeleporter(std::istream &input_stream) noexcept {
  input_stream.tie(0);
  std::ios::sync_with_stdio(false);
  Teleporter *teleporter = new Teleporter();

  int64_t number_of_towns, number_of_teleportations;
  input_stream >> number_of_towns >> number_of_teleportations;

  teleporter->SetNumberOfTowns(number_of_towns);
  for (int64_t from = 1; from <= number_of_towns; ++from) {
    int32_t to;
    input_stream >> to;
    teleporter->SetMapping(from, to);
  }

  constexpr int64_t kInitialTown = 1;
  const int64_t final_town = teleporter->SearchFinalTown(kInitialTown, number_of_teleportations);
  std::cout << final_town << std::endl;

  delete teleporter;
}

Teleporter::Teleporter() noexcept : number_of_towns_(0) {}

Teleporter::~Teleporter() noexcept {}

void Teleporter::SetNumberOfTowns(const int64_t number_of_towns) noexcept {
  number_of_towns_ = number_of_towns;
  for (int64_t i = 0; i <= number_of_towns; ++i) {
    visited_time_[i] = -1;
  }
}
void Teleporter::SetMapping(const int64_t from, const int64_t to) noexcept {
  ported_to_[from] = to;
}

int64_t Teleporter::SearchFinalTown(const int64_t start_town, const int64_t number_of_teleportations) noexcept {
  int64_t offset = -1;
  int64_t cycle = -1;
  int64_t c_town = start_town;
  visited_time_[start_town] = 0;
  for (int64_t i = 1; i <= number_of_towns_ + 1; ++i) {
    c_town = ported_to_[c_town];
    if (visited_time_[c_town] >= 0) {
      cycle = i - visited_time_[c_town];
      offset = visited_time_[c_town];
      break;
    }
    visited_time_[c_town] = i;
  }
  const int64_t modified_k = (number_of_teleportations > offset)
                                 ? ((number_of_teleportations - offset) % cycle) + offset
                                 : number_of_teleportations;
  c_town = start_town;
  for (int64_t i = 1; i <= modified_k; ++i) {
    c_town = ported_to_[c_town];
  }
  return c_town;
}

int main() {
  try {
    CallTeleporter(std::cin);
  } catch (...) {
    std::cerr << "ERROR: main()" << std::endl;
  }
  return 0;
}


Measured memory_bytes: 6372
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

const int MAX = 20000;
const int INF = (1<<20);

int data[MAX];
int n,r;
ll sum;

void solve(){
  for(int i = 0; i < n; i++){
    int *pos = upper_bound(data+i+1,data+n,r-data[i]);
    if(*pos != INF) sum += &data[n]-pos;
  }
}

int main(){
  while(cin >> n >> r && n+r){
    sum = 0;
    fill(data,data+MAX,INF);
    for(int i = 0; i < n; i++) cin >> data[i];
    sort(data,data+MAX);
    solve();
    cout << sum << endl;
  }
}

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

using namespace std;

int main(){
	string s;
	cin >> s;
	bool flag = true;
	if(s[0] != 'A') flag = false;
	int cnt = 0, pos = 0;
	for(int i = 2; i < (int)s.size() - 1; i++){
		if(s[i] == 'C'){
			cnt++;
			pos = i;
		}
	}
	if(cnt != 1) flag = false;
	for(int i = 1; i < (int)s.size(); i++){
		if(i != pos and isupper(s[i])) flag = false;
	}
	
	if(flag) cout << "AC" << endl;
	else cout << "WA" << endl;
	return 0;
}

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

long long L[87];

int main() {
  int N;
  cin >> N;
  
  L[0] =2;
  L[1] =1;
  for (int i = 2;i < 87;i++) {
    L[i] = L[i-1] + L[i-2];
    //cout << L[i] << endl;
  }
  
  cout << L[N] << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;
typedef pair<Int, Int> p;
const Int INF = 1e18;

struct edge{Int to, t;};

Int N, M, S;

// 頂点vで銀貨c枚持っている状態を頂点 v*2501+c とする 
vector<vector<edge>> G(51*2501);
vector<Int> dist(51*2501, INF);

void dijkstra(int s){
    // first:最短距離 second:頂点番号
    priority_queue<p, vector<p>, greater<p>> q;
    dist[s] = 0;
    q.push(p(0, s));

    while (!q.empty()){
        int cur_d = q.top().first;
        int cur_v = q.top().second;
        q.pop();

        if (cur_d > dist[cur_v]) continue;

        for (int i = 0; i < G[cur_v].size(); i++){
            edge e = G[cur_v][i];
            if (dist[cur_v] + e.t < dist[e.to]){
                dist[e.to] = dist[cur_v] + e.t;
                q.push(p(dist[e.to], e.to));
            }
        }
    }
}


int main(){
    cin >> N >> M >> S;
    if(S > 2500) S = 2500;

    rep(i,M){
        int u, v; Int a, b;
        cin >> u >> v >> a >> b;
        u--; v--;

        for(int j=a; j<=2500; j++){
            G[u*2501+j].push_back(edge{v*2501+(j-a),b});
            G[v*2501+j].push_back(edge{u*2501+(j-a),b});
        }
    }

    
    rep(i,N){
        Int c, d; cin >> c >> d;
        for(int j=0; j+c<=2500; j++){
            G[i*2501+j].push_back(edge{i*2501+(j+c),d});
        }
    }

    dijkstra(S);

    rep1(i,N-1){
        Int ans = INF;
        rep(j,2501){
            ans = min(ans, dist[i*2501+j]);
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 23732
#include<cstdio>
#include<cstring>
#include<bits/stdc++.h>
#include<iostream>
#include<math.h>
#include<fstream>
#define sc(x) scanf("%d",&x)
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORd(i,a,b) for(int i=a;i>b;i--)
#define ff first
#define ss second
#define reset(x) memset(x,0,sizeof x)
#define sz(x) x.size()
#define pb push_back
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);


using namespace std;

typedef pair<int,int> pii;
typedef vector<pii> vii;
const int con = 1e5+7;
static const int INF = 0x3f3f3f3f;
static const int MOD = 1e9+7;


int main() {

    int n,m;cin >> n >> m;
    vector<int> arr(m);

    FOR(i,0,m)
        cin >> arr[i];

    sort(arr.begin(),arr.end());
    vector<int> ans(m-1);

    FOR(i,1,m){
        ans[i-1] = arr[i]-arr[i-1];
    }
    sort(ans.begin(),ans.end());
    ll a=0;
    FOR(i,0,m-n){
        a += ans[i];
    }
    cout << a;
}

Measured memory_bytes: 1024
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	ll x, k, d;
	cin >> x >> k >> d;
	if(x < 0){
		ll nm = -x / d;
		if(-x / d >= k){
			cout << abs(x + (k * d)) << endl;
		}
		else{
			if((k - nm) & 1){
				cout << abs(x + ((nm + 1) * d)) << endl;
			}
			else{
				cout << abs(x + (nm * d)) << endl;
			}
		}
	}
	else{
		ll nm = x / d;
		if(x / d >= k){
			cout << abs(x - (k * d)) << endl;
		}
		else{
			if((k - nm) & 1){
				cout << abs(x - ((nm + 1) * d)) << endl;
			}
			else{
				cout << abs(x - (nm * d)) << endl;
			}
		}
	}
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


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

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

int main()
{
    int a,b;
    while(cin>>a>>b)
    {
         int k=gcd(a,b);
         int m=a/k*b;
         cout<<k<<" "<<m<<endl;
   }
 return 0;
}

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



int main(){
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> edges[100000];
    for(int i=0; i<M; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        edges[a].emplace_back(b, 1);
        edges[b].emplace_back(a, 2);
    }

    vector<int> col(N, -1);
    int64_t ans = 0;
    for(int s=0; s<N; s++) if(col[s] == -1){
        queue<int> que;
        que.push(s);
        col[s] = 0;
        vector<int64_t> num(3);
        bool cont = false;
        int es = 0;
        while(que.size()){
            int i = que.front(); que.pop();
            num[col[i]]++;
            for(auto& e : edges[i]){
                int j = e.first, c = (col[i] + e.second) % 3;
                if(e.second == 1) es++;
                if(col[j] == -1){
                    col[j] = c;
                    que.push(j);
                }else if(col[j] != c){
                    cont = true;
                }
            }
        }
        if(cont){
            int64_t s = num[0] + num[1] + num[2];
            ans += s*s;
        }else if(num[0] && num[1] && num[2]){
            ans += num[0]*num[1] + num[1]*num[2] + num[2]*num[0];
        }else{
            ans += es;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 7284
#include<cstdio>
#include<map>
#include<iostream>
#include<queue>
using namespace std;
map<string,int>f;
map<string,bool>ff;
queue<string>Q;
int main()
{
	string s,t;
	int ans=0;
	int a,b;
	scanf("%d",&a);
	for(int i=1;i<=a;i++) {
		cin>>s;
		f[s]++;
		if(!ff[s]) {
			ff[s]=1;
			Q.push(s);
		}
	}
	scanf("%d",&b);
	for(int i=1;i<=b;i++) {
		cin>>t;
		f[t]--;
		if(!!ff[t]) {
			ff[t]=1;
			Q.push(t);
		}
	}
	while(!Q.empty()) {
		string fff=Q.front();
		Q.pop();
		ans=max(ans,f[fff]);
	}
	printf("%d",ans);//
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#include<functional>
#define INF 1 << 30
using namespace std;
typedef pair<int, int> PII;
typedef priority_queue<PII, vector<PII>, greater<PII> > PQ;

int root[101][101], n, k; //not use 0;

void newboat()
{
	int c, d, e;
	cin >> c >> d >> e;
	if (root[c][d] > e)	root[c][d] = root[d][c] = e;
	return;
}

int solve()
{
	int a, b;
	cin >> a >> b;
	bool though[101][101]; //not use 0;
	PQ cand;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++) though[i][j] = false;
	}

	cand.push(make_pair(0, a));
	while (!cand.empty()){
		PII now = cand.top();
		cand.pop();
		if (now.second == b) return now.first;

		for (int i = 1; i <= n; i++){
			if (root[now.second][i] != INF && !though[now.second][i]){
				though[now.second][i] = though[i][now.second] = true;
				cand.push(make_pair(now.first + root[now.second][i], i));
			}
		}
	}
	return -1;
}

int main()
{
	while (true){
		cin >> n >> k;
		if (!n && !k) break;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++) root[i][j] = INF;
		}
		for (int i = 0; i < k; i++){
			bool in;
			cin >> in;
			if (in) newboat();
			else cout << solve() << endl;
		}
	}
	return 0;
}

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

const int MAXN = 500010;
typedef long long LL;
LL n, Q, D, f[MAXN], ansl[MAXN], A[MAXN];
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n >> D;
	for (int i = 1; i <= n; ++i) std::cin >> A[i];
	f[n + 1] = D - 1;
	for (int i = n; i; --i) {
		if (f[i + 1] + A[i] >= D * 2 - f[i + 1]) f[i] = f[i + 1];
		else f[i] = f[i + 1] - A[i];
	}
	int now = 0;
	for (int i = 1; i <= n; ++i) {
		ansl[i] = now <= f[i + 1] || now >= D * 2 - f[i + 1];
		if (now < D)
		now = now + A[i] >= D * 2 - now ? now : now + A[i];
		else
		now = now - A[i] <= D * 2 - now ? now : now - A[i];
	}
	std::cin >> Q;
	while (Q --> 0) {
		int t; std::cin >> t;
		std::cout << (ansl[t] ? "YES" : "NO") << '\n';
	}
	return 0;
}


Measured memory_bytes: 13696
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(void)
{
  int n,l[101],i,j,k,ans=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&l[i]);
  }
  for(i=0;i<n-2;i++){
    for(j=i+1;j<n-1;j++){
      for(k=j+1;k<n;k++){
        if(l[i]!=l[j]&&l[i]!=l[k]&&l[j]!=l[k]){
          if(l[i]<l[j]+l[k]&&l[j]<l[i]+l[k]&&l[k]<l[i]+l[j]){
          ans++;
          }
        }
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}
  

Measured memory_bytes: 1732
a = raw_input().split()
n = int(a[0])
m = int(a[1])

C = map(int,raw_input().split())
T = [float('inf') for _ in xrange(n+1)]

def getTheNumberOfCoin():
    T[0] = 0
    for i in xrange(m):
        for j in xrange(C[i],n+1):
            T[j] = min(T[j], T[j-C[i]]+1)

    print T[n]
    return 0

getTheNumberOfCoin()

Measured memory_bytes: 9152
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
    int N;
    ll W;
    cin >> N >> W;
    ll w[N],v[N];
    REP(i,N){
        cin >> w[i] >> v[i];
    }
    vector<ll> sum[4];
    REP(i,4){
        sum[i].push_back(0);
    }
    REP(i,N){
        sum[w[i] - w[0]].push_back(v[i]);
    }
    REP(i,4){
        sort(sum[i].begin() + 1, sum[i].end());
        reverse(sum[i].begin() + 1, sum[i].end());
    }
    REP(i,4){
        REP(j,sum[i].size() - 1){
            sum[i][j + 1] += sum[i][j];
        }
    }
    ll ans = 0;
    for(int i = 0; i < sum[0].size(); i++){
        for(int j = 0; j < sum[1].size(); j++){
            for(int k = 0; k < sum[2].size(); k++){
                for(int l = 0; l < sum[3].size(); l++){
                    if(w[0] * i + (w[0] + 1) * j + (w[0] + 2) * k + (w[0] + 3) * l > W){
                        continue;
                    }
                    ans = max(ans, sum[0][i] + sum[1][j] + sum[2][k] + sum[3][l]);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        for (int i =0;  i < n; i++ ) {
            x[i] = sc.nextInt();
        }
        int sum = 0;
        int min = 0;
        for (int p =1; p<= 100; p++){
            for (int i = 0; i< n; i++){
                sum = (int) (sum + Math.pow(x[i] - p, 2));
            }
            if (p == 1){
                min = sum;
            } else if (sum < min) {
                min = sum;
            }
            sum = 0;
        }
        System.out.println(min);
    }
}


Measured memory_bytes: 21844
s_list=[]
while True:
    s = input()#文字列
    if s == "-":
        break
    shuffle = int(input())
    for i in range(shuffle):
        h=int(input())
        s = s[h:]+s[:h]
    s_list.append(s)
for i in range(len(s_list)):
    print(s_list[i])


Measured memory_bytes: 5600
using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static void Main()
    {
        var s = Console.ReadLine();

        var count = new Dictionary<char, int>();
        foreach (var c in s)
        {
            if (!count.ContainsKey(c))
            {
                count[c] = 0;
            }
            count[c]++;
        }

        var ok = count.Count == 2 && count.All(kv => kv.Value == 2);

        Console.WriteLine(ok ? "Yes" : "No");
    }
}

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

int main(){
  int N;
  int x = 0;
  cin >> N;
  vector<int> a(N);
  for(int i = 0; i < N; i++){
    cin >> a[i];
  }
  sort(a.begin(),a.end());
  for(int i = N-1; i >= 0; i--){
    if(N%2 == 0){
      if(i%2 == 0){
        a[i] = -a[i];
      }
      x += a[i];
    }
    else{
      if(i%2 == 1){
        a[i] = -a[i];
      }
      x += a[i];
    }
  }
  cout << x << endl;
}


Measured memory_bytes: 256
t=str(input())
k=int(input())
L = len(t)
tmp = t[0]
n = 0 #change
flag = 0
for i in range(1,L):
  if flag==1:
    flag=0
  elif t[i]==tmp:
    n+=1
    flag=1  
  tmp=t[i]
ans=k*n
if L>2:
  if t[0]==t[-1] and flag==0:
    u = t[0]+t
    tmp = u[0]
    m = 0 #change
    flag = 0
    for i in range(1,L+1):
      if flag==1:
        flag=0
      elif u[i]==tmp:
        m+=1
        flag=1  
      tmp=u[i]
    if m!=n: 
      ans+=k-1

if t.count(t[0])==L:
  ans=(k*L)//2
print(ans)


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

typedef long long LL;
typedef long double LD;
typedef pair < int, int > PII;
typedef pair < LL, LL > PLL;
typedef pair < LD, LD > PDD;

#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
template < typename _T > inline void _DBG(const char *s, _T x) { cerr << s << " = " << x << "\n"; }
template < typename _T, typename... args > void _DBG(const char *s, _T x, args... a) { while(*s != ',') cerr << *s++; cerr << " = " << x << ','; _DBG(s + 1, a...); }

#ifdef LOCAL
#define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define DBG(...) (__VA_ARGS__)
#define cerr if(0) cout
#endif

// ********************** CODE ********************** //

int main()
{
    _upgrade
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            int ile = i * m + j * n - 2 * i * j;
            if(ile == k)
            {
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
	return 0;
}


Measured memory_bytes: 256
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
a = sorted(a)
gra = []
for i in range(n):
  a[i].append(i)
for i in range(n-1):
  gra.append([a[i][2],a[i+1][2],a[i+1][0]-a[i][0]])
a = sorted(a,key= lambda x:x[1])
for i in range(n-1):
  gra.append([a[i][2],a[i+1][2],a[i+1][1]-a[i][1]])
union = [0] *  n
uc = 0
ans = 0
gra = sorted(gra, key = lambda x: x[2])
class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return
uni = UnionFind(n)
for i in range(len(gra)):
  hen = gra[i]
  if (uni.find(hen[0]) != uni.find(hen[1])):
    ans += hen[2]
    uni.union(hen[0],hen[1])
    uc += 1
  if uc == n-1:
    break
print(ans)

Measured memory_bytes: 57312
#include <stdio.h>
typedef long long ll;

int abs(int a) {
  return a > 0 ? a : -a;
}

int main(void) {
  int i, j, k, n;
  scanf("%d", &n);
  ll a[n], sum[n + 1];
  for(i = 0; i < n; ++i) {
    scanf("%lld", &a[i]);
    if(i) sum[i] = sum[i - 1] + abs(a[i] - a[i - 1]);
    else sum[i] = abs(a[i]);
  }
  sum[n] = sum[n - 1] + abs(a[n - 1]);
  for(i = 0; i < n; ++i) {
    ll ans = sum[n];
    if(i && i != n - 1) {
       ans -= abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i]);
       ans += abs(a[i + 1] - a[i - 1]);
    } else if(!i){
      ans -= sum[0] + abs(a[1] - a[0]);
      ans += abs(a[1]);
    } else {
      ans -= abs(a[i] - a[i - 1]) + abs(a[i]);
      ans += abs(a[i - 1]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}

Measured memory_bytes: 2688
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <limits.h>
#include <map>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    
    long long N, T;
    vector<long long> t;
    long long sum = 0;
    
    cin >> N;
    cin >> T;
    
    for ( int i = 0; i < N; i++ ) {
        long long temp;
        cin >> temp;
        t.push_back( temp );
    }
    
    sum = t[0];
    
    for ( int i = 1; i < N; i++ ) {
        long long time = t[i] - t[i-1];
        if ( time <= T ) {
            sum += time;
        }
        else {
            sum += T;
        }
    }
    
    sum += T;
    
    cout << sum << endl;
    
    return 0;
    
}

Measured memory_bytes: 2420
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    mod = 10 ** 9 + 7

    q = deque([0])
    ans = k
    seen = [False] * n
    seen[0] = True

    while q:
        v = q.popleft()
        if v == 0:
            cand = k - 1
        else:
            cand = k - 2
        for n_v in g[v]:
            if not seen[n_v]:
                seen[n_v] = True
                ans = (ans * cand) % mod
                cand -= 1
                q.append(n_v)

    print(ans)


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


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

int main() {
	int n;
	string s;
	cin >> n >> s;
	if(n % 2 != 0) cout << "No" << endl;
	else {
		int j = s.size() / 2;
		for(int i = 0; i < (s.size() / 2); i++) {
			if(s[i] != s[j]) {
				cout << "No" << endl;
				return 0;
			}
			j++;
		}
		cout << "Yes" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef pair<ll , ll> lli;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;
typedef vector<lli> vlli;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define PI 3.14159265359
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)

const ll mod = 1000000007;
const ll maxn = (ll)2e5+5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
const ll INF = 1e18;

ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};


void solve(){
	ll n , k;
	cin >> n >> k;
	ll step[n+5] , a[n+5] , p[n+5];
	f1(n) cin >> a[i];
	mem(step , -1);
	mem(p , -1);
	p[1] = 0;
	step[0] = 1;
	ll pos = 1;
	while(1){
		if(k == 0){
			cout << pos;
			return;
		}
		if(p[a[pos]] != -1){
			k--; 
			ll total = abs(p[a[pos]] - p[pos]) + 1;
			ll head = k%total;
			//cout << total << ' ' << head << '\n';
			cout << step[ p[a[pos]]+ head];
			return; 
		}
		k--;
		p[a[pos]] = p[pos]+1;
		step[p[pos]+1] = a[pos];
		pos = a[pos];
	}
	return;
}


int main() {
   
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    ll T;
    T=1;
    //cin >> T;
    //scanf("%lld",&T);
    ll CT = 0;
    //work();
    while(T--){
    	//cout << "Case " << ++CT <<": " ;
    	//printf("Case %lld: ",++CT);
		solve();
	}
    
    return 0;
}


Measured memory_bytes: 8280
n = int(input())
s = input()
ans = ''
c = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for i in range(len(s)):
    char = s[i]
    idx = c.index(char)
    new_idx = (idx + n) % 26
    ans += c[new_idx]
print(ans)

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

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
ll n;
cin>>n;
if(n%2==1){
    cout<<n*(n-1)/2<<endl;
}
else{
    cout<<n*(n/2-1)+n/2<<endl;
}
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main(){
    int h1, h2, m1, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    cout << (h2 * 60 + m2 - k - h1 * 60 - m1) << endl;
    return 0;
}

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



int main()
{
    int n;
    cin >> n;
    map<string,int> mp;

    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        mp[s]++;
    }
    cin >> n;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        mp[s]--;
    }
    int res=0;
    for(auto it : mp)
    {
        res=max(res, it.second);
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 256
c = []
for i in range(3):
	ctemp = list(map(int,input().split()))
	c.append(ctemp)
temp = [c[0][0],c[1][0],c[2][0]]
a = [-100000,0,0]
b = [0,0,0]
check = False
while a[0] <= 100000:
	tempcheck = True
	b[0] = c[0][0] - a[0]
	b[1] = c[0][1] - a[0]
	b[2] = c[0][2] - a[0]
	a[1] = c[1][0] - b[0]
	a[2] = c[2][0] - b[0]
	for i in range(3):
		for k in range(3):
			if c[i][k] != a[i] + b[k]:
				tempcheck = False
	if tempcheck:
		check = True
	a[0] += 1

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

Measured memory_bytes: 3064
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const long long MAXN=100005;
long long n;
long long d[MAXN],rd[MAXN],yd[MAXN];
vector<int>w[MAXN];
long long key=0;
void dfs(long long u,long long f)
{
	if(key)
		return ;
	long long cnt=0,MX=0,e=0;
	for(long long i=0;i<int(w[u].size());i++)
	{
		long long v=w[u][i];
		if(v!=f)
		{
			e=1;
			dfs(v,u);
			cnt+=d[v];
			MX=max(MX,d[v]);
		}
	}
	if(!e)
		return ;
	if(key)
		return ;
	if(d[u]>cnt)
	{
		key=1;
		return ;
	}
	long long o=cnt-d[u];
	long long yb=min(cnt/2,cnt-MX);
	if(yb<o)
	{
		key=1;
		return ;
	}
	d[u]=cnt-2*o;
	if(d[u]<0)
	{
		key=1;
		return ;
	}
}
int main()
{
	//freopen("tree.in","r",stdin);
	//freopen("tree.out","w",stdout);
	scanf("%lld",&n);
	for(long long i=1;i<=n;i++)
		scanf("%lld",&yd[i]);
	for(long long i=1;i<n;i++)
	{
		long long u,v;
		scanf("%lld %lld",&u,&v);
		w[u].push_back(v);
		w[v].push_back(u);
		rd[u]++;
		rd[v]++;
	}
	//for(long long i=1;i<=n;i++)
	//	d[i]=yd[i];
	//dfs(1,0);
	for(long long i=1;i<=n;i++)
		d[i]=yd[i];
	dfs(n,0);
	if(key)
		printf("NO\n");
	else
		printf("YES\n");
	fclose(stdin);
	fclose(stdout);
}

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

int main(){
    int h,n; cin >> h >> n;
    int sum=0;
    rep(i,n){
        int a; cin >> a;
        sum+=a;
    }
    if(h<=sum) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <deque>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define eb emplace_back
#define ep emplace
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2 vector<vec>
#define vecll2 vector<vecll>
#define vec3 vector<vec2d>
#define vecll3 vector<vecll2d>
#define fi first
#define se second
#define endl "\n"
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
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 T> inline void print(vector<T> v){for(T e:v)cout<<e<<" ";cout<<endl;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
void print(vector<vec> v){for(auto e:v){for(auto ee:e)cout<<ee<<" ";cout<<endl;}}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}
const ll INF=1e17;

main(){
    int n=in();
    map<int,int> mp;
    rep(i,n){
        mp[in()]++;
    }
    vec v;
    for(auto e:mp)v.pb(e.second);
    sort(all(v));
    vec cnt(n+2);
    for(auto e:v)cnt[e]++;
    vec rui(n+2),rui2(n+2);
    rui[0]=rui2[0]=0;
    rep(i,n+1)rui[i+1]+=rui[i]+cnt[i]*i;
    rep(i,n+1)rui2[i+1]+=cnt[i]+rui2[i];
    // print(rui);
    // print(rui2);
    rep2(i,1,n){
        int l=0,r=n+1;
        while(l<r-1){
            int mid=(l+r)/2;
            int b=rui2[n+1]-rui2[mid];
            int c=rui[mid];
            if((i-b)*mid <=c)l=mid;
            else r=mid;
            // cout<<i<<" "<<mid<<" "<<b<<" "<<c<<endl;
        }
        cout<<l<<endl;
    }
}

Measured memory_bytes: 19056
#include<bits/stdc++.h>
#define PI 3.141592653589
#define ll long long
using namespace std;

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

  ans = min(a, k);
  k -= min(a, k);

  ans += min(b, k)*0;
  k -= min(b, k);

  ans -= min(c, k);

  cout << ans;
  
  return 0;
}

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


    typedef long long ll;



    
    const int mx = 105;
    const int mx1 = 1000001;
    const ll mod = 1000000007;

   vector<vector<int> >edges;
    void adds(int &a, int b){
        a+= b;
        if(a >= mod)
        a-=mod;
    }
    int mul(int a, int b){
        return (ll) a * b % mod;
    }

    // void subs(int &a, int b){
    //     a-= b;
    //     if(a < 0)
    //      a+=mod;
    // }

    pair<int, int> dfs(int a, int p){
        
        int col_black = 1;
        int col_white = 1;
        for(int b:edges[a]){
            if(b != p){
                pair<int, int> p1 = dfs(b, a);
                
                col_black = mul(col_black, p1.second);
                col_white = mul(col_white, (p1.second + p1.first)%mod);
            }
        }
      //  cout<<a<<" "<<col_black<<" "<<col_white<<"\n";
        return make_pair(col_black, col_white);
        
    }
int main(){
    int n, i, j, a, b;

    cin>>n;
    edges.clear();
    edges.resize(n);

    for(i = 0;i < n-1;i++){
        cin>>a>>b;
        edges[a-1].push_back(b-1);
        edges[b-1].push_back(a-1);
    }
    pair<int, int> res = dfs(0, -1);
    cout<<(res.first+res.second)%mod<<"\n";

}

Measured memory_bytes: 12672