akhauriyash/Code-Regression huggingface dataset:
// Problem: B - Multiple of 9
// Contest: AtCoder - AtCoder Beginner Contest 176
// URL: https://atcoder.jp/contests/abc176/tasks/abc176_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
 
using namespace std;
#define int long long
#define ll long long
const int N = 2e5+5;
const int mod = 1e9;
#define ld long double
#define PI 3.14159265358979323846
const int INF = 10000000;
 
void flash()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(9);
}
 
//3. Structure or classes
//3. Ends here
 
//1. Data structures declaration here
//1. Ends here
 
//2. Extra Functions here
//2. Ends here
 
 
void solve();
int32_t main()
{
    flash();
    int t;
    t = 1;
    //cin>>t;
    while(t--){
        solve();
        //cout<<"\n";
    }
    return 0;
}
 
 
 
void solve()
{
	string s;
	cin>>s;
	
	int sum=0;
	for(auto c:s){
		sum+=(c-'0');
	}
	
	if(sum%9==0){
		cout<<"Yes\n";
	}
	else cout<<"No\n";
    return;
}
// how r u bro

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

#define int long long
#define REP(i, l, r) for (int i=(l); i<(r); ++i)
#define RREP(i, r, l) for (int i=(r); i>(l); --i)
#define popcount __builtin_popcountll

const int INF = 1LL<<60;
const int MOD = 1000000007;

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> t) {
    return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> t) {
    return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";
}

template <typename A>
string to_string(vector<A> v) {
    bool first = true;
    string result = "[";
    for (A i : v) {
        if (!first) result += ", ";
        first = false;
        result += to_string(i); 
    }
    return result + "]";
}

template <typename A>
string to_string(A x[], int n) {
    string result = "{";
    REP(i, 0, n) {
        if (i!=0) result += ", ";
        result += to_string(x[i]); 
    }
    return result + "}";
}

string bin_string(int x) {
    const int d = 64;
    string result(d, ' ');
    RREP(i, d-1, -1) result[d-1-i] = '0'+((x&1LL<<i)!=0);
    return result;
}

vector<int> getZ(string s) {
    int n = s.size();
    vector<int> z(n);
    int x = 0, y = 0;
    REP(i, 1, n) {
        z[i] = max(0LL, min(z[i-x], y-i+1));
        while (i+z[i] < n && s[z[i]] == s[i+z[i]]) {
            x = i;
            y = i+z[i];
            ++z[i];
        }
    }
    return z;
}

int powa(int base, int exp) {
    if (exp<=0) return 1;
    if (base<=0) return 0;
    int val = powa(base, exp>>1);
    val = val*val % MOD;
    if (exp&1) {
        val = val*base % MOD;
    }
    return val;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int R,C;
    cin >> R >> C;
    int grid[R][C];

    REP(r, 0, R) REP(c, 0, C) cin >> grid[r][c];
    REP(r, 0, R) REP(c, 0, C) {
        int x;
        cin >> x;
        grid[r][c] = abs(grid[r][c]-x);
    }

    const int BIG = 80*160+10;
    bitset<2*BIG> dp[C];
    dp[0][BIG+grid[0][0]] = dp[0][BIG-grid[0][0]] = 1;
    REP(r, 0, R) REP(c, 0, C) {
        if (r == 0 && c == 0) continue;
        dp[c] = dp[c]<<grid[r][c] | dp[c]>>grid[r][c];
        if (c!=0) dp[c] |= dp[c-1]<<grid[r][c] | dp[c-1]>>grid[r][c];
    }

    int res=0;
    while (!dp[C-1][BIG+res]) ++res;
    cout << res;
}

Measured memory_bytes: 640
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int main()
{
	int n,total=0;
	cin>>n;
	char s[51];
	for(int j=1;j<=n;j++)
		cin>>s[j];
	for(int i=1;i<=n;i++)
		if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C')
			total++;
	cout<<total<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
  int n;
  cin>>n;
  string s;
  cin>>s;
  int i=0,count=0;
  while(i<n)
  {
    if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')
      count++;
    i++;
  }
  cout<<count;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include <string>
#include <math.h>
#include <queue>
#include <stack>
#define cinf(n,x,y) for(int i=0;i<(n);i++) cin >> x[i] >>y[i];
typedef long long int ll;
using namespace std;

int main(){
  string s;
  bool ok;
  while(1){
    stack<char> stk;
    ok=true;
    getline(cin,s);
    if(s==".")break;
    for(int i=0;i<s.size();i++){
      if(s[i]=='(')stk.push('(');
      else if(s[i]=='[') stk.push('[');
      else if(s[i]==')'){
        if(stk.empty()||stk.top()!='('){
          ok=false;
          break;
        }
        else stk.pop();
      }
      else if(s[i]==']'){
        if(stk.empty()||stk.top()!='['){
          ok=false;
          break;
        }
        else stk.pop();
      }
    }
    cout << (ok&&stk.empty()?"yes":"no") << endl;
  }
}


Measured memory_bytes: 3144
#include <stdio.h>
#include <string.h>
#define LEN 100005
 
typedef struct pp {
  char name[100];
  int t;
} P;
 
P Q[LEN];
int head, tail, n;
 
void enqueue(P x) {
  Q[tail] = x;
  tail = (tail + 1) % LEN;
}
 
P dequeue() {
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;
}
 
int min(int a,int b) {
  return a < b ? a : b; 
}
 
int main() {
  int elaps = 0, c;
  int i, q;
  P u;
  char str[64];
  
  scanf("%d %d",&n ,&q);
  for(i=1; i<=n; i++) {
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1; tail = n + 1;
 
  while(head != tail) {
    u = dequeue();
    c = min(q, u.t);
    u.t -= c;
    elaps += c;
    if(u.t > 0) enqueue(u);
    else {
      printf("%s %d\n",u.name,elaps);
    }
  }
  return 0;
}


Measured memory_bytes: 11860
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);
#define ll long long int

using namespace std;

int main(){_
    map<ll,ll> quant;
    ll n,q,total = 0;
    cin >> n;
    for(ll i=0;i<n;i++){
        ll r;
        cin >> r;
        if(quant.find(r) == quant.end()) quant[r] = 0;
        quant[r] += 1;
        total += r;
    }
    cin >> q;
    for(ll i=0;i<q;i++){
        ll a,b;
        cin >> a >> b;
        if(quant.find(a) != quant.end()){
            ll cont = quant[a];
            total = total - (a*cont);
            quant[a] = 0;
            if(quant.find(b) == quant.end()) quant[b] = cont;
            else quant[b] += cont;
            total = total + (b*cont);
        }
        cout << total << endl;
    }
    return 0;
}


Measured memory_bytes: 8756
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll N,X,M,S;
  cin >> N >> X >> M;
  ll m[M],n[M+1];
  S=X;
  for(ll i=0;i<M;i++)m[i]=-1;
  m[X]=1;
  n[1]=X;
  for(ll i=2;i<=N;i++){
    X=(X*X)%M;
    if(m[X]!=-1){
      ll y=(N-i+1)/(i-m[X]);
      if(y>0){
        ll o=0;
        for(ll j=m[X];j<i;j++)o+=n[j];
        S+=o*y;
      }
      ll l=(N-i+1)%(i-m[X]);
      for(ll j=m[X];j<m[X]+l;j++)S+=n[j];
     cout << S;
      return 0;
    }
    m[X]=i;
    n[i]=X;
    S+=X;
  }
  cout << S;
}

Measured memory_bytes: 4700
#include <algorithm>
#include <iostream>
#include <map>
#include <string>

using namespace std;

long long n, ans;
map<string, long long> words;

int main()
{
  cin >> n;
  
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    words[s]++;
  }
  
  for (auto p: words) {
    ans += p.second * (p.second - 1) / 2;
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11136
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
int dp[2][105];
int can[2][105];
int n;
int pick(int x, int y)
{
    if (x==1&&y==n-1)
    {
        return can[x][y];
    }
    if (dp[x][y]!=-1)return dp[x][y];
    if (x!=1)dp[x][y]=pick(x+1,y);
    if (y+1<n)dp[x][y]=max(dp[x][y],pick(x,y+1));
    dp[x][y]+=can[x][y];
    return dp[x][y];
}
int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        dp[0][i]=-1;
        dp[1][i]=-1;
        cin>>can[0][i];
    }
    for (int i=0;i<n;i++)
    {
        cin>>can[1][i];
    }
    printf ("%d\n",pick(0,0));
}

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

struct res{string city; int s,ii;}re[102];
bool cmp(res a, res b)
{
	if (a.city!=b.city) return a.city<b.city;
	return a.s>b.s;
 } 
int main()
{
    int n; cin>>n;
    for (int i=1; i<=n; i++)
    {
    	cin>>re[i].city>>re[i].s;
    	re[i].ii=i;
	}
	sort(re+1,re+n+1,cmp);
	
	for (int i=1; i<=n; i++) cout <<re[i].ii<<endl;
 } 

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>
int min(int a, int b) { return a < b ? a : b; }
int main(){
    int i,n,ans=0,mini=1000000,p[200020]={};
    scanf("%d",&n);
    for(i=0; i<n; i++){
        scanf("%d",&p[i]);
    }
    for(i=0; i<n; i++){
        if(p[i]<=mini)ans++;
        mini=min(mini,p[i]);
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 2492
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

long long int gcd(long long int x, long long int y)
{
	if (y == 0) { return x; }
	return gcd(y, x % y);
}

int main(void)
{
	int n;
	cin >> n;
	vector<int> x(n);
	for (int i = 0; i < n; i++) { cin >> x[i]; }
	int L = x[0], R = x[0];
	for (int i = 0; i < n; i++)
	{
		L = min(L, x[i]);
		R = max(R, x[i]);
	}

	int ans = 10000000;
	for (int i = L; i <= R; i++)
	{
		int cost = 0;
		for (int j = 0; j < n; j++)
		{
			cost += (x[j] - i) * (x[j] - i);
		}
		ans = min(ans, cost);
	}

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

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

int main() {
  int N;
  cin >> N;
int A[N];
  int result = 0;
  A[0] = 1000000;
  for(int a = 1;a < N;a++)cin >> A[a];
  A[N] = 1000000;
  for(int a = 0;a < N;a++){
    result += min(A[a],A[a+1]);
  }
  


cout<<result<<endl;
}

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

using namespace std;
const int N = 3e5 + 5;
int main() {
#ifndef ONLINE_JUDGE
//	freopen("input.in", "r", stdin);
#endif
	int n, k;
	scanf("%d %d", &n, &k);
	vector<int> pos, neg;
	pos.push_back(0);
	for (int i = 0; i < n; ++i) {
		int a;
		scanf("%d", &a);
		if (a >= 0)
			pos.push_back(a);
		else
			neg.push_back(a);
	}
	int res = 2e9;
	if (pos.size() > k)
		res = pos[k];
	for (int i = 0; i < pos.size(); ++i) {
		int j = (int) neg.size() - k + i;
		if (0 <= j && j < neg.size()) {
			res = min(res, min(pos[i] * 2 - neg[j], pos[i] - neg[j] * 2));
		}
	}
	printf("%d\n", res);
	return 0;
}

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

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

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

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

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

    int N;
    cin >> N;

    vi vals(N);
    int pos = -1, neg = -1;
    for (int i = 0; i < N; i++) {
        cin >> vals[i];

        if (neg == -1 || vals[i] < vals[neg]) neg = i;
        if (pos == -1 || vals[i] > vals[pos]) pos = i;
    }

    if (neg == pos) {
        neg = 0;
        pos = 1;
        assert(vals[neg] == vals[pos]);
    }

    int pp = vals[pos], nn = vals[neg];

    vector<array<int, 2>> ops;
    for (int i = 0; i < N; i++) if (i != pos && i != neg) {
        if (vals[i] < 0) { ops.push_back({ pp, vals[i] }); pp -= vals[i]; }
        if (vals[i] >= 0) { ops.push_back({ nn, vals[i] }); nn -= vals[i]; }
    }
    ops.push_back({ pp, nn });

    cout << ops.back()[0] - ops.back()[1] << "\n";
    for (auto v : ops)
        cout << v[0] << " " << v[1] << "\n";

    return 0;
}



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

int main() {
  int k;
  cin >> k;
  string s;
  cin >> s;
  int n = s.size();
  if (n <= k) {
    cout << s << endl;
  }
  else {
    cout << s.substr(0, k) << "..." << endl;
  }
}


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

int main(){
  char c;
  cin >> c;
  if (c == 'a' || c== 'i'|| c== 'u'||c == 'e'||c == 'o'){
    cout << "vowel" << endl;
  }

  else{
    cout << "consonant" << endl;
  }
}

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

using namespace std;
using ll = long long;

int main (void){
  int n, m;

  cin >> n >> m;

  if(abs(n - m) > 1){
    cout << 0 << endl;
    return 0;
  }

  ll saru = 1;
  ll inu = 1;

  const ll md = 1000000007;
  for (int i = 1; i <= n; i++){
    inu *= i;
    if(inu >= md) inu %= md;
  }
  for (int i = 1; i <= m; i++){
    saru *= i;
    if(saru >= md) saru %= md;
  }
  if(n == m) cout << inu * 2 % md * saru % md << endl;
  else cout << inu * saru % md << endl;
  return 0;
}
  


Measured memory_bytes: 256
/*
ID: Aman Raj
LANG: C++
TASK: preface
*/
#include<iostream>
#include <stdio.h>
//#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#include<math.h>
typedef  long long int ll;
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
//#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
//#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <fstream>
// find_by_order()  // order_of_key
typedef tree<
	int,
	null_type,
	less<int>,
	rb_tree_tag,
	tree_order_statistics_node_update>
	ordered_set;

	   //vector<ll > vten(7),vfive(7),vfifty(7),vhundred(7),vfivehundred(7),vthousand(7);

int main()
{
      ifstream fin("preface.in");
      ofstream fout("preface.out");
      ll n;cin>>n;cout<<(n-2)*180;

	return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

const (
	SENTINEL = 2000000000
)

func main() {
	fmt.Println(answer(os.Stdin))
}

func answer(r io.Reader) int {
	sc := bufio.NewScanner(r)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	A := make([]int, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		A[i], _ = strconv.Atoi(sc.Text())
	}
	return mergeSort(A, n, 0, n)
}

func merge(A []int, n, left, mid, right int) int {
	n1 := mid - left
	n2 := right - mid
	L, R := make([]int, n1+1), make([]int, n2+1)
	for i := 0; i < n1; i++ {
		L[i] = A[left+i]
	}
	for i := 0; i < n2; i++ {
		R[i] = A[mid+i]
	}
	L[n1], R[n2] = SENTINEL, SENTINEL

	cnt := 0
	i, j := 0, 0
	for k := left; k < right; k++ {
		if L[i] <= R[j] {
			A[k] = L[i]
			i++
			continue
		}
		A[k] = R[j]
		j++
		cnt += n1 - i
	}
	return cnt
}

func mergeSort(A []int, n, left, right int) int {
	if left+1 < right {
		mid := (left + right) / 2
		v1 := mergeSort(A, n, left, mid)
		v2 := mergeSort(A, n, mid, right)
		v3 := merge(A, n, left, mid, right)
		return v1 + v2 + v3
	}
	return 0
}



Measured memory_bytes: 8528
#include<bits/stdc++.h>
#define lson l, mid, i<<1
#define rson mid+1, r, i<<1|1
#define PII pair<int, int>
#define Size(x) (int)(x.size())
using namespace std;
typedef long long LL;
//const int MOD = 1e9+7;
const auto INF = 0x3f3f3f3f;
const int N = 2e5+5;
const double pri = acos(-1.0);
struct node {
    int x, y;
}A, B, E[N], Ans[N];

bool cmp1(const struct node &u, const struct node &v) {
    if(u.x == v.x)
        return u.y < v.y;
    return u.x < v.x;
}

bool cmp2(const struct node &u, const struct node &v) {
    if(u.x == v.x)
        return u.y < v.y;
    return u.x > v.x;
}

int b[N];

int main() {
    double p1 = (double)10*pri;
    double p2 = (double)5*pri;
    int n;
    scanf("%d%d%d%d", &A.x, &A.y, &B.x, &B.y);
    scanf("%d", &n);
    int x1 = min(A.x, B.x), x2 = max(A.x, B.x);
    int y1 = min(A.y, B.y), y2 = max(A.y, B.y);
    int cnt = 0;
    for(int i=1; i<=n; i++) {
        scanf("%d%d", &E[i].x, &E[i].y);
        if(E[i].x >= x1 && E[i].x <= x2 && E[i].y >= y1 && E[i].y <= y2) {
            Ans[++cnt] = E[i];
        }
    }
    if(A.y > B.y)
        swap(A, B);
    if(A.x < B.x)
        sort(Ans+1, Ans+1+cnt, cmp1);
    else
        sort(Ans+1, Ans+1+cnt, cmp2);
    int len = 1;
    b[1] = Ans[1].y;
    for(int i=2; i<=cnt; i++) {
        if(Ans[i].y > b[len]) {
            b[++len] = Ans[i].y;
        } else {
            int pos = (int)(lower_bound(b+1, b+1+len, Ans[i].y) - b);
            b[pos] = Ans[i].y;
        }
    }
    if(cnt == 0)
        len = 0;
    double answer = (double)100*(double)(y2 - y1 + x2 - x1);
    if(len == x2-x1+1 || len == y2-y1+1) {
        len--;
        answer += (double)len * p2 - (double)len * 20.0;
        answer += p1 - 20;
    } else
        answer += (double)len * p2 - (double)len * 20.0;
    printf("%.11lf\n", answer);
}

/*

0 0 2 3
2
1 1
2 2

*/







Measured memory_bytes: 4096
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int a;
    cin >> a;
    int ans = 0;
    while(a != 0){
        if(a%10 == 1) ans++;
        a /= 10;
    } 
    cout << ans << endl;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
string s;
ll a[30];
int main()
{
	while(cin>>s)
	{
		memset(a,0,sizeof(a));
		ll n=s.length();
		for(int i=0;s[i];i++)
			a[s[i]-'a']++;
		ll ans=n*(n-1)/2+1;
		for(int i=0;i<26;i++)
			ans-=a[i]*(a[i]-1)/2;//cout<<a[i]<<endl;
		cout<<ans<<endl;	
	}
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (int)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }

template< typename T >
class BinaryIndexedTree{
    private:
        vector<T> array;

    public:
        // Constructer
        BinaryIndexedTree(long long sz){
            array.assign(++sz, 0LL);
        }

        // Culuclate sum in the inclusive range [0,k]
        T sum(long long k) {
            T ret = 0;
            for (++k; k > 0; k -= k & -k) ret += array[k];
            return (ret);
        }

        // Add x to k th element
        void add(long long k, T x){
            for (++k; k < array.size(); k += k & -k) array[k] += x;
        }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    ll N,Q;
    cin >> N >> Q;
    
    BinaryIndexedTree<ll> BIT(N);
    
    rep(_,Q){
        ll c,x,y;
        cin >> c >> x >> y;
        if(!c) BIT.add(x-1,y);
        else print(BIT.sum(y-1)-BIT.sum(x-2));
    }
    

    return 0;
}



Measured memory_bytes: 3532
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	int tmp = n;
	bool ok = true;
	while (1) {
		if (tmp & 1) {
			if (tmp == 1)
				ok = false;
			break;
		}
		tmp = tmp >> 1;
	}
	if (n == 2) ok = false;
	if (ok) {
		cout << "Yes" << E;
		for (int i = 1; i < 3; i++) {
			cout << i << " " << i + 1 << E;
			cout << n + i << " " << n + i + 1 << E;
		}
		cout << 3 << " " << n + 1 << E;
		for (int i = 4; i + 1 <= n; i += 2) {
			cout << i << " " << i + 1 << E;
			cout << i + 1 << " " << 1 << E;
			cout << 1 << " " << n + i << E;
			cout << n + i << " " << n + i + 1 << E;
		}
		if (n % 2 == 0) {
			int tmp = 1;
			while (!(n & tmp)) {
				tmp = tmp << 1;
			}
			int a = n - tmp + 1;
			cout << a << " " << n << E;
			cout << tmp + n << " " << n + n << E;
		}
	}
	else {
		cout << "No" << E;
	}
	//system("pause");
	return 0;
}


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

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    ll x = 0;
    for (ll i = 2; i < N; i++) x ^= A[i];
    
    ll sum = A[0]+A[1];
    
    if (sum < x || (sum-x)%2 == 1) {
        cout << -1 << endl;
        return 0;
    }
    
    ll b = (sum-x)/2;
    if (b > A[0]) {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 50; i >= 0; i--) {
        if ((b>>i)&1LL) continue;
        if (((x>>i)&1LL) == 0) continue;
        if (b+(1LL<<i) > A[0]) continue;
        b += (1LL<<i);
    }
    
    if (b == 0 || (b^(sum-b)) != x) {
        cout << -1 << endl;
        return 0;
    }
    
    cout << A[0]-b << endl;
    return 0;
}


Measured memory_bytes: 3628
#include "bits/stdc++.h"
using namespace std;
int swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    swap(a, b);
    swap(a, c);
    cout << a << " " << b << " " << c << endl;
    return 0;
}

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

int main(){
  int n,m,x[100000];
  int s[100001]={},c[100001]={},ans=0;
  cin>>n>>m;
  for(int i=0;i<n;i++)cin>>x[i],s[x[i]%m]++,c[x[i]]++;
  for(int i=0;i<=m/2;i++){
    if(i==0)ans+=s[i]/2,s[i]%=2;
    else if(m%2==0&&i==m/2)ans+=s[i]/2,s[i]%=2;
    else{
      int M=min(s[i],s[m-i]);
      ans+=M;
      s[i]-=M,s[m-i]-=M;
    }
  }
  for(int i=0;i<=1e5;i++){
    if(s[i%m]>=2&&c[i]>=2){
      int M=min(c[i],s[i%m]);
      s[i%m]-=M/2*2;
      ans+=M/2;
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

int main() {
	int n,l;
	cin>>n>>l;
	string a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	for(int i=0;i<n;i++){
		cout<<a[i];
	}
}

Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)
        
n,m = map(int,input().split())
L = list(map(int,input().split()))

UFind = UnionFind(n)
for i in range(m):
    a,b = map(int,input().split())
    UFind.union(a-1,b-1) 
cnt = 0   

for i in range(n):
    if UFind.same_check(i,L[i]-1):
        cnt +=1
print(cnt)

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

using namespace std;

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


Measured memory_bytes: 3084
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))


H,W,M=map(int, input().split())
#P = [list(map(int,input().split())) for i in range(M)]
Hlist=[0] * M
Wlist=[0] * M
P = []
for i in range(M):
    Hlist[i],Wlist[i]=map(int, input().split())
    P.append([Hlist[i],Wlist[i]])

Pset = set(map(tuple, P))

HC = Counter(Hlist)
HD = HC.most_common()
WC = Counter(Wlist)
WD = WC.most_common()

Hmax = HD[0][1]
Wmax = WD[0][1]
ans = Hmax + Wmax

# print(P)
# print(Pset)
# print("H----")
# print(Hlist)
# print(HC)
# print(HD)
# print("Hmax=",Hmax)
# print("W----")
# print(Wlist)
# print(WC)
# print(WD)
# print("Wmax=",Wmax)

# print(ans)


for i in range(len(HD)):
    if HD[i][1] != Hmax:
        break
    for j in range(len(WD)):
        if WD[j][1] != Wmax:
            break
        tmp = tuple([HD[i][0],WD[j][0]])
        if (tmp in Pset) == False:
            print(ans)
            sys.exit()
        
print(ans-1)


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

const int INF = 1000000000;

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

    vector<vector<int>> dp(N + 1, vector<int>(H + 10000, INF));
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < H + 10000; j++) {
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - A[i]] + B[i]);
        }
    }

    int res = INF;
    for (int j = H; j < H + 10000; j++) {
        res = min(res, dp[N][j]);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 78592
import java.util.Scanner;

class Main
{
	private static StringBuffer map[];
	private static int count;
	static int[] dx = {0, 1, 0 ,-1};
	static int[] dy = {-1, 0, 1, 0};
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		while (true)
		{
			int n = sc.nextInt(), m = sc.nextInt();
			if (n == 0 && m == 0) break;
			map = new StringBuffer[m];
			count = 0;
			int x = 0, y = 0;
			for (int i = 0; i < m; i++)
			{
				String str = sc.next();
				if (str.indexOf('@') != -1)
				{
					x = str.indexOf('@');
					y = i;
				}
				map[i] = new StringBuffer(str);
			}
			walk(x, y);
			System.out.println(count);
		}
	}
	private static void walk(int x, int y)
	{
		count++;
		map[y].setCharAt(x, '#');
		for (int i = 0; i < 4; i++)
		{
			try{
				if (map[y+dy[i]].charAt(x+dx[i]) == '.') walk(x+dx[i], y+dy[i]);
			}catch (IndexOutOfBoundsException e){}
		}
	}
}

Measured memory_bytes: 12000
#define _USE_MATH_DEFINES
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<long long>> VVLL;
typedef vector<vector<bool>> VVB;
typedef vector<vector<double>> VVD;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) (a).begin(),(a).end()

const int MOD = 1000000007;

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

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

void debug(VI &arr){
	int n=arr.size();
	rep(i,n){
		cout<<arr.at(i)<<endl;
	}
}

void debug(VVI &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout << board.at(i).at(j) << " ";
		}
		cout<<endl;
	}
}

void debug(VVLL &board){
	int h = board.size();
	int w = board.size();
	rep(i,h){
		rep(j,w){
			cout<<board.at(i).at(j)<<" ";
		}
		cout<<endl;
	}
}

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

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

int main(){
	cout<<fixed;
	//cout<<setprecision(9)<<...
	double a,b,x;
	cin>>a>>b>>x;
	double ans=0;
	if(x==a*a*b){
		cout<<ans<<endl;
		return 0;
	}
	if(x>=a*a*b/2){
		ans=atan(pow(a,3)/(2*(pow(a,2)*b-x)));
		ans=ans/M_PI*180;
		cout<<setprecision(9)<<90-ans<<endl;
		return 0;
	}
	ans=atan(2*x/a/pow(b,2));
	ans=ans/M_PI*180;
	cout<<setprecision(9)<<90-ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = int64_t;
using ull = uint64_t;

constexpr ll INF = 1000000000;/* 1e+9a */

class Repeater{
    int st;
    int ed;
    int d;
public:
    class rep_iterator{
        int i; int d;
    public:
        rep_iterator(int x, int pd) :i(x), d(pd) {}

        int& operator*(){ return i; }
        bool operator==(const rep_iterator& k) const { return i == k.i; }
        bool operator!=(const rep_iterator& k) const { return i != k.i; }
        rep_iterator& operator++(){ i+=d; return *this; }
    };

    Repeater(int N) :st(0), ed(N), d(1) {}
    Repeater(int b, int e) :st(b), ed(e), d(1) {if(st > ed){ st--; ed--; d = -1; } }
    Repeater(int b, int e, int dif) :st(b), ed(e), d(dif) {}

    rep_iterator begin() const{ return rep_iterator(st, d); }
    rep_iterator end() const{ return rep_iterator(ed, d); }

};

template<class T, class Compare> using p_queue = priority_queue<T, vector<T>, Compare>;
template<class T> using min_queue = p_queue<T, greater<T>>;
template<class T> using max_queue = p_queue<T, less<T>>;

template<class T> bool min_update(T& X, const T& A){ if(X > A) {X = A; return true;} return false; }
template<class T> bool max_update(T& X, const T& A){ if(X < A) {X = A; return true;} return false; }

void sub_main(istream &cin) {
    ll N;
    cin >> N;
    if(!cin) return;
    vector<ll> A(N), B(N);
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        A.push_back(a); B.push_back(b);
    }// i
    vector<pair<ll, int>> Bi;
    Bi.reserve(A.size());
    for (int i = 0; i < A.size(); ++i) {
        Bi.emplace_back(B[i], i);
    }// i
    sort(Bi.begin(), Bi.end(), greater<>());
    
    ll endt = INF;
    for (auto &&bp : Bi) {
        int i = bp.second;
        ll b = bp.first;
        endt = min(endt, b);
        endt -= A[i];
    } // bp
    
    cout << (endt < 0 ? "No" : "Yes") << endl;
    
    

}

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef DEBUG
    cerr << "DEBUG MODE" << endl;
    string test_cases = "test_D.txt";
    auto fs = fstream(test_cases, fstream::in);
    int lp = 0;
    while(fs) {
        lp++;
        cout << lp <<  "#------\n";
        sub_main(fs);
    }
    cout << "------#" << endl;
    if(lp <= 1) sub_main(cin);
#else
    sub_main(cin);
#endif
    return 0;
}


Measured memory_bytes: 12744
class Time
 
  # 1???????§???¨?¨?
  MINUTE_SECOND = 60
 
  #1??????????§???¨?¨?
  HOUR_SECOND = 3600
 
  def initialize(second)
    self.convertTimeFromSecond(second)
  end
 
  # ?§???°????????????????§?????????????????????£????????????????´?????????????
  def convertTimeFromSecond(second)
 
    # ?????????????§??????????????¨????????????????????????????
    @hour = second / HOUR_SECOND
    surplus = second % HOUR_SECOND
 
    # ????¨??????????????????????????¨????????????????????????????
    @minute = surplus / MINUTE_SECOND
    surplus = surplus % MINUTE_SECOND
 
    # ????¨?????????????????§?????¨????
    @second = surplus
  end
 
  def getHour()
    return @hour
  end
 
  def getMinute()
    return @minute
  end
 
  def getSecond()
    return @second
  end
 
end
 
timeInstance = Time.new(gets.chomp.to_i)
puts timeInstance.getHour.to_s + ":" + timeInstance.getMinute.to_s + ":" + timeInstance.getSecond.to_s

Measured memory_bytes: 8708
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    int n,c;
    cin>>n;
    if(n%1000==0)
        cout<<"0"<<endl;
    else
    {
        c=n%1000;
        cout<<1000-c<<endl;
    }

    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define asll unsigned long long
#define ll long long //20190711
#define pii pair<int,int>
#define st first
#define nd second
#define jn <<" "<< 			//20190830
#define ml <<endl; 			//20190831->20190903
#define co cout<<           //20190903
asll M=1e9+7;				//20190518->20190821
int n;						//20190831

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	srand(time(0));			//20190709
	cin>>n;
	int a=(1000-(n%1000))%1000;
	cout<<a<<endl; 
}



Measured memory_bytes: 3588
import sys
input = sys.stdin.readline

n = int(input())
s = list(input())
res = 10**9

cta = 0
ctb = 0
a = [0]*n
b = [0]*n
for i in range(n):
    if s[i] == '.':
        cta += 1
    else:
        ctb += 1
    a[i] = cta
    b[i] = ctb
for i in range(n):
    res = min(res,b[i]+a[-1]-a[i])
res = min(res,a[-1],b[-1])
print(res)

Measured memory_bytes: 14184
#include <iostream>

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <tuple>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

using namespace std;

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

//math
//-------------------------------------------
template <class T>
inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

//repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0, sizeof(a))

//debug
// #define dump(x) cerr << #x << " = " << (x) << endl;
// #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
//                       << " " << __FILE__ << endl;

int main()
{
    map<string, long> sub_strs;

    LL N;
    cin >> N;

    string S;
    cin >> S;

    LL size = S.size();
    LL max_len = 0;

    vector<vector<bool>> counted(size, vector<bool>(size, false));

    FOR(i, 0, size)
    {
        for (int j = i + 1; j < size; j++)
        {
            if (S[i] == S[j] && !counted[i][j])
            {
                LL len = 0;
                for (int k = 0; k < j - i; k++)
                {
                    if (S[i + k] == S[j + k])
                    {
                        counted[i][k] = true;
                        len++;
                    }
                    else
                    {
                        break;
                    }
                }
                FOR(l, 0, len)
                {
                    counted[i + l][j + l] = true;
                }
                max_len = max(max_len, len);
            }
        }
    }

    cout << max_len << endl;
}

Measured memory_bytes: 3456
package main

import (
	"fmt"
)

func main() {
	var a, b, c, d float64
	fmt.Scan(&a, &b, &c, &d)
	var res float64
	if b-c <= 0 || d-a <= 0 {
		res = 0
	} else {
		if a <= c && b >= d {
			res = d - c
		} else if a >= c && b <= d {
			res = b - a
		} else if a >= c && b >= d {
			res = d - a
		} else {
			res = b - c
		}
	}
	fmt.Println(res)
}


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

const int MAXN = 100005;
const int INF = 1<<28;
int N;
string S;
int dp[MAXN][9][9][2];

int getPosX(int k) {
  return (k - 1) % 3;
}

bool ok(int l, int r) {
  return getPosX(l) <= getPosX(r);
}

int main() {
  while(cin >> S && S != "#") {
    N = S.size();
    fill(dp[0][0][0], dp[MAXN][0][0], INF);
    for(int l = 1; l <= 9; ++l) {
      for(int r = 1; r <= 9; ++r) {
        if(ok(l, r)) dp[0][l][r][0] = dp[0][l][r][1] = 0;
      }
    }
    for(int i = 0; i < N; ++i) {
      for(int l = 1; l <= 9; ++l) {
        for(int r = 1; r <= 9; ++r) {
          for(int j = 0; j < 2; ++j) {
            int p = S[i] - '0';
            if(ok(p, r)) {
              dp[i+1][p][r][0] = min(dp[i+1][p][r][0],
                                     dp[i][l][r][j] + (j == 0));
            }
            if(ok(l, p)) {
              dp[i+1][l][p][1] = min(dp[i+1][l][p][1],
                                     dp[i][l][r][j] + (j == 1));
            }
          }
        }
      }
    }
    int res = INF;
    for(int l = 1; l <= 9; ++l) {
      for(int r = 1; r <= 9; ++r) {
        for(int j = 0; j < 2; ++j) {
          res = min(res, dp[N][l][r][j]);
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}

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

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

using namespace std;
using lint=long long;

const long long INF=1LL<<61;

template<class T> struct edge{
	int to;
	T wt;
	edge(int to,const T& wt):to(to),wt(wt){}
};
template<class T> using weighted_graph=vector<vector<edge<T>>>;

template<class T>
void add_undirected_edge(weighted_graph<T>& G,int u,int v,const T& wt){
	G[u].emplace_back(v,wt);
	G[v].emplace_back(u,wt);
}

int main(){
	int h,w,n; scanf("%d%d%d",&h,&w,&n);
	weighted_graph<lint> G(h+w);
	rep(i,n){
		int y,x;
		lint a; scanf("%d%d%lld",&y,&x,&a); y--; x--;
		add_undirected_edge(G,y,h+x,a);
	}

	vector<lint> val(h+w);
	vector<bool> vis(h+w);
	rep(u,h+w) if(!vis[u]) {
		vis[u]=true;
		val[u]=0;

		lint row_min=INF,col_min=INF;
		queue<int> Q; Q.emplace(u);
		while(!Q.empty()){
			int v=Q.front(); Q.pop();

			if(v<h) row_min=min(row_min,val[v]);
			else    col_min=min(col_min,val[v]);

			for(auto e:G[v]){
				if(!vis[e.to]){
					vis[e.to]=true;
					val[e.to]=e.wt-val[v];
					Q.emplace(e.to);
				}
				else{
					if(val[v]+val[e.to]!=e.wt) return puts("No"),0;
				}
			}
		}

		if(row_min+col_min<0) return puts("No"),0;
	}
	puts("Yes");

	return 0;
}


Measured memory_bytes: 15908
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 500 * 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;

int n;
long long k;
long long a[N], b[N], c[N];

bool read() {
    if (!(cin >> n >> k))
        return false;

    for (int i = 0; i < n; ++i)
        cin >> a[i];
 
    return true;
}
 
void solve() {
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            if (a[j] > a[i]) {
                ++b[i];

                if (j < i)
                    ++c[i];
            }

        ans += k * c[i] % MOD + ((k * (k - 1) / 2) % MOD) * b[i] % MOD;
        ans %= MOD;
    }

    cout << ans << endl;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    while (read())
        solve();
 
    return 0;
}
 


Measured memory_bytes: 4480
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a, b;
        int me[][] = new int [3][2];
        int flg = 0;
        for(int i = 0; i < n; i++){
            a = sc.nextInt();
            b = sc.nextInt();
            me[i % 3][0] = a;
            me[i % 3][1] = b;
            if(i > 1){
                if(me[0][0] == me[0][1] && me[1][0] == me[1][1] && me[2][0] == me[2][1]){
                    System.out.println("Yes");
                    flg += 1;
                    break;
                }
            }
        }
        if(flg == 0){
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 36000
#include <bits/stdc++.h>
using namespace std;
struct node {
  int v;
  int depth;
  node *l,*r,*p;
};

string s[3];
int dpnum[1000]={0};
node *tree[3];

string encode(node *x,node *y);
void decode(int num,int n,int dep,node *par);

int main(){
  cin >> s[0] >> s[1];
  //s[0]="(()[6]())[8](((()[4]())[7]())[9]())";
  for(int i=0;i<3;i++){
    tree[i]=new node;
    tree[i]->p=NULL;
    tree[i]->l=NULL;
    tree[i]->r=NULL;
    tree[i]->depth=0;
    tree[i]->v=-1;
  }
  decode(0,0,0,tree[0]);
  //cout << tree[0]->v <<" "<<tree[0]->l->v << " "<< tree[0]->r->v<<" "<<tree[0]->r->l->v <<" "<< tree[0]->r->l->l->v<<endl;
  decode(1,0,0,tree[1]);
  cout << encode(tree[0],tree[1]) << endl;
  return 0;
}

void decode(int num,int n,int dep,node *par){
  //cout << n << " " << s[num][n] << " "<<dep <<" " << par->v << endl;
  if(n==s[num].size())return;
  if(s[num][n]=='('){
    node *newnode = new node;
    newnode->r=NULL;
    newnode->l=NULL;
    newnode->p=par;
    newnode->depth=dep+1;
    newnode->v=-1;
    if(n!=0&&s[num][n-1]==']'){
      par->r=newnode;
    }
    else {
      par->l=newnode;
    }
    decode(num,n+1,dep+1,newnode);
  }
  else if(s[num][n]==')')decode(num,n+1,dep-1,par->p);
  else if(s[num][n]=='['){
    int x=0;
    while(s[num][n+1]>='0'&&s[num][n+1]<='9'){
      n++;
      x*=10;
      x+=s[num][n]-'0';
    }
    par->v=x;
    //cout <<"in "<<dep << par->v <<endl;
    decode(num,n+2,dep,par);
  }
}

string encode(node *x,node *y){
  string ansl,ansm,ansr;
  if(x->l==NULL||y->l==NULL||x->l->v==-1||y->l->v==-1)ansl="()";
  else ansl = encode(x->l,y->l);
  if(x->r==NULL||y->r==NULL||x->r->v==-1||y->r->v==-1)ansr="()";
  else ansr = encode(x->r,y->r);
  ansm="["+to_string(x->v+y->v)+"]";
  if(x==tree[0])return ansl+ansm+ansr;
  else return "("+ansl+ansm+ansr+")";
}



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

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

    vector<long long> divisors;
    for (long long i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            divisors.push_back(i);
            if (i != N / i) {
                divisors.push_back(N / i);
            }
        }
    }

    long long res = 0;
    for (int i = 0; i < divisors.size(); i++) {
        long long m = divisors[i] - 1;
        if (m == 0) continue;
        if (N / m == N % m)
            res += m;
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 384
N, Q = map(int, input().split())
S = input()
l = [0]*Q
r = [0]*Q

sum_arr = [0, 0]

for i in range(Q):
    l[i], r[i] = map(int, input().split())

for i in range(N-1):
    if S[i:i+2] == "AC":
        sum_arr.append(sum_arr[-1] + 1)
    else:
        sum_arr.append(sum_arr[-1])
for i in range(Q):
    print(sum_arr[r[i]] - sum_arr[l[i]])


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

int main() {
  string n;
  getline(cin,n);
  for(int i=0;i<3;i++){
    if(n.at(i) == '1'){
      n.at(i) = '9';
    }
    else{
      n.at(i) = '1';
    }
  }
  cout << n << endl;
}


Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) {
		try(Scanner scanner = new Scanner(System.in)) {

			String data = scanner.nextLine();

			int K = Integer.parseInt(data);
			int x = 7 % K;
			Set<Integer> s = new HashSet<Integer>();
			int i = 1;
			int ans = -1;

			while (!s.contains(x)) {
				if (x == 0) {
					ans = i;
					break;
				}

				s.add(x);
				x = (x * 10 + 7) % K;
				i++;
			}

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

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define LOOP(i) while(i--)
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

vector<string> split_naive(const string &s,vector<char>& delim) {
	vector<string> elems;
	string item;
	for(char ch:s){
		bool exist = false;
		for(auto del:delim){
			if(ch==del){
				if(!item.empty()) elems.push_back(item);
				item.clear();
				exist = true;
				break;
			}
		}
		if(!exist){
			item += ch;
		}
	}
	if(!item.empty()) elems.push_back(item);
	return elems;
}

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

	char str[1030];
	vector<char> delim={' ',',','.'};
	vector<string> S;
	while(cin.getline(str,sizeof(str))){
		auto T = split_naive(str,delim);
		for(auto u:T){
			if(u.size()>=3 && u.size()<=6) S.push_back(u);
		}
	}
	int N=S.size();
	REP(i,N-1){
		cout << S[i] << ' ';
	}
	if(!S.empty()) out(S.back());
	return 0;
}


Measured memory_bytes: 3080
n, m = map(int, input().split())
X = []
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    X.append((b, a))

X.sort()
c = -1
ans = 0
for i in range(m):
    b, a = X[i]
    if a < c:
        continue
    else:
        ans += 1
    c = b
print(ans)


Measured memory_bytes: 53336
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long a,b,c=0,d=0,m;
  cin>>a>>b>>c;
  if(a+b<c) cout<<c-a-b<<"\n";
  else{
    if(a+b>=c && c+a>=b) cout<<"0\n";
    else{
      cout<<b-a-c<<"\n";
    }
  }
  return(0);
}


Measured memory_bytes: 256