akhauriyash/Code-Regression huggingface dataset:
# 解説を見た

# https://tjkendev.github.io/procon-library/python/range_query/bit.html
# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


def main():
    from itertools import accumulate
    import sys

    input = sys.stdin.readline

    N, K = map(int, input().split())
    A = (int(input()) - K for _ in range(N))

    acc = (0,) + tuple(accumulate(A))

    def compress(iter):
        convert = {x: i for i, x in enumerate(sorted(iter), start=1)}
        # BITで扱うので、1-indexedにする
        # 値kがa番目とa+1番目に含まれているとき、k:a->k:a+1で上書きされる
        return (convert[x] for x in iter)

    comacc = compress(acc)

    ret = 0

    b = BIT(N + 1)
    for x in comacc:
        ret += b.sum(x)
        b.add(x, 1)

    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 37980
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()) {
			int N = sc.nextInt(), K = sc.nextInt();
			System.out.println(K == 1 ? 0 : N - K);
		}
	}
}

Measured memory_bytes: 21972
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <numeric>
#include <bitset>
using namespace std;
#define lint long long
#define ll long long
#define pq priority_queue
long long INF = 100000000000000000;
#define pii pair<long long,long long>
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
/******************************define*********************************/

/*****************************functions********************************/

/****************************main function*****************************/
int main(void) {
	ll N; cin >> N;
	vector<ll> x(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i];
	}
	/*累積和を求める*/
	vector<ll> cum;
	cum.push_back(x[0]);
	for (int i = 1; i < x.size(); i++) {
		cum.push_back(cum[i - 1] + x[i]);
	}
	cum.push_back(0);
	sort(all(cum));
	ll ans = 0;
	vector<ll> k;
	ll y = 0;
	cum.push_back(INF);
	//for (int i = 0; i < cum.size(); i++) cout << cum[i] << endl;
	for (int i = 1; i < cum.size(); i++) {
		if (cum[i] == cum[i - 1]) {
			y++;
		}
		else {
			k.push_back(y + 1);
			y = 0;
		}
	}
	
	for (int i = 0; i < k.size(); i++) {
		//cout << k[i] << endl;
		ans += k[i]* (k[i] - 1) / 2;
	}
	cout << ans << endl;
	return 0;

}


Measured memory_bytes: 6384
#include "bits/stdc++.h"
using namespace std;
 
int x,ans;
vector<int> nums;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	for(int i=2;i<=1000;i++){
		for(int j=2;j<=1000;j++){
			if(pow(i, j) > 1000)
				break;
			nums.push_back(pow(i,j));
		}
	}
	nums.push_back(1);
	sort(nums.begin(),nums.end());
	cin>>x;
	for(int i=0;i<nums.size();i++){
		if(nums[i] <= x)
			ans = nums[i];
		else break;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 384
from typing import SupportsComplex


N, x = [int(a) for a in input().split()]
a = [int(a) for a in input().split()]
a = sorted(a)

result = []
for v in a:
    if x >= v:
        result.append(v)
        x -= v
    else:
        break

if len(result) == 0:
    print(0)
    exit()

if (x > 0) and (len(result) == len(a)):
    result[-1] += x

if result[-1] != a[len(result)-1]:
    ans = len(result)-1
else:
    ans = len(result)

print(ans)

Measured memory_bytes: 10164
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)
#define rem(i,n,x) for(int i=n;i>x;i--)
#define SORT(x) sort(x.begin(),x.end())
#define rev(x) reverse(x.begin(),x.end())
#define all(x) x.begin(),x.end()
#define pb push_back
#define setp(x) setprecision(x)
using ll = long long;
using ull = unsigned long long;

int main() {
	int a, b;
	cin >> a >> b;

	int k = abs(a + b);
	if (k % 2 == 1) cout << "IMPOSSIBLE" << endl;
	else cout << k / 2 << endl;

	return 0;
}

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

int main()
{
  int a,b;
  char x;

  while(true)
    {
      int k = 0;
      
      cin >> a >> x >> b;
      
      if(x == '+')
	{
	  k = a + b;
	}
      if(x == '-')
	{
	  k = a - b;
	}
      if(x == '*')
	{
	  k = a * b;
	}
      if(x == '/')
	{
	  k = a / b;
	}
      if(x == '?')
	{
	  break;
	}
      cout << k << endl;
    }

  return 0;
}



Measured memory_bytes: 3084
x1,y1,x2,y2=gets.split.map(&:to_i)

x3 = x2 + (y1 - y2)
y3 = y2 + (x2 - x1)

x4 = x3 + (y2 - y3)
y4 = y3 + (x3 - x2)

puts "#{x3} #{y3} #{x4} #{y4}"


Measured memory_bytes: 1788
import numpy as np
import math 
n = int(input())

s = np.zeros(3) # *3,*6

s[0] = n*(n+1)//2
for i in np.arange(n)+1:
  for j in np.arange(i+1,n+1):
    s[1] += math.gcd(i,j)
    for k in np.arange(j+1, n+1):
      s[2] += math.gcd(math.gcd(i,j),k)
print(int(sum(s*[1,6,6])))

Measured memory_bytes: 27316
import java.math.BigInteger;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		BigInteger A = new BigInteger(sc.next()), B = new BigInteger(sc.next());
		sc.close();
		System.out.println(A.multiply(B));
	}
}


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

int h[100004];
int dp[100004];

void solve(){
    int n,k;
    cin >> n >> k;
    // int h[n];
    for(int i = 0 ; i < n ; i++)
        cin >> h[i];
    
    // int dp[n];
    dp[n-1] = 0;
    // dp[n-2] = abs(h[n-1] - h[n-2]);
    
    for(int i = n-2 ; i >= 0 ; i--){
        dp[i] = dp[i+1] + abs(h[i+1]-h[i]);
        for(int j = 2 ; j <= k ; j++){
           if(i+j >= n){
               break;
           }
           else{
               dp[i] = min(dp[i], dp[i+j] + abs(h[i+j]-h[i]));
           }
        }
    }
    
    cout << dp[0];
    
}

int main(){
   solve();
}




Measured memory_bytes: 4416
R, C, K = map(int, input().split())
values = [[0] * C for i in range(R)]
for i in range(K):
	r, c, v = map(int, input().split())
	values[r - 1][c - 1] = v

dp = [[[0] * C for i in range(R)] for j in range(4)]

dp[1][0][0] = values[0][0]

for i in range(R):
	for j in range(C):
		if values[i][j] == 0:
			if j != 0:
				for k in range(4):
					dp[k][i][j] = max(dp[k][i][j], dp[k][i][j - 1])
			if i != 0:
				for k in range(4):
					dp[0][i][j] = max(dp[0][i][j], dp[k][i - 1][j])
		else:
			#取る
			if j != 0:
				for k in range(1, 4):
					dp[k][i][j] = max(dp[k][i][j], dp[k - 1][i][j - 1] + values[i][j])
			if i != 0:
				for k in range(4):
					dp[1][i][j] = max(dp[1][i][j], dp[k][i - 1][j] + values[i][j])
			#取らん
			if j != 0:
				for k in range(4):
					dp[k][i][j] = max(dp[k][i][j], dp[k][i][j - 1])
			if i != 0:
				for k in range(4):
					dp[0][i][j] = max(dp[0][i][j], dp[k][i - 1][j])

ans = 0
for k in range(4):
	ans = max(ans, dp[k][-1][-1])
print(ans)

Measured memory_bytes: 429816
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=405;
const int M=100005;
int vis[405][405];
pair<int,int> xjt[M];
int gg[N];
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	rep(i,1,m)scanf("%d%d",&xjt[i].first,&xjt[i].second);
	rep(i,1,n)
	{
		vis[i][i]=1;gg[i]=0;
		per(j,m,1)
		{
			if(vis[i][xjt[j].first] && vis[i][xjt[j].second]){gg[i]=1;break;}
			if(vis[i][xjt[j].first]) vis[i][xjt[j].second]=1;
			else if(vis[i][xjt[j].second]) vis[i][xjt[j].first]=1;
		}
	}
	int ans=0;
	rep(i,1,n)if(!gg[i])rep(j,i+1,n)if(!gg[j])
	{
		int fg=1;
		rep(k,1,n)if(vis[i][k] && vis[j][k]) {fg=0;break;}ans+=fg;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

int main() {
    // 標準入力
    int R,G,B,N;
    cin >> R >> G>> B >> N;
    int ans=0;
    for (int r=0; r*R<=N; r++) {
        for (int g=0; (r*R)+(g*G)<=N; g++) {
            if ((N-((r*R)+(g*G)))%B==0) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}


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

bool check(string inPut, string target) {
	bool res = true;
	map<char, char> mp;
	for (int i = 0; i < inPut.size(); i++) {
		if (mp.count(inPut[i])) {
			if (mp[inPut[i]] != target[i]) {
				res = false;
			}
		}
		mp[inPut[i]] = target[i];
	}
	return res;
}

int main() {
	
	string s, t; cin >> s >> t;
	bool can1 = check(s, t);
	bool can2 = check(t, s);
	if (can1 && can2) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 4172
r,g,b,n=map(int, input().split())
r,g,b=sorted([r,g,b],reverse=True)
ans=0
for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if (n-i*r-j*g)%b==0:
            ans+=1
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;


//
int main(void){
	//FILE* fp_in = freopen("data.txt", "r", stdin);

	while(1){
		int pts[] = {0,0};
		int a,b,n;
		cin >> n;
		if(n == 0) break;
		for(int i = 0; i < n; i ++) {
			cin >> a >> b;
			if(a > b) {
				pts[0] += (a+b);
			} else if(a < b) {
				pts[1] += (a+b);
			} else {
				pts[0] += a;
				pts[1] += b;
			}
		}
		cout << pts[0] << " " << pts[1] << endl;

	}

	//while(1){}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
typedef long long ll;
typedef vector<ll> vl;
#define rp(i, f, t) for (int i = f; i < t; i++)
#define pr(i, f, t) for (int i = t - 1; i >= f; i--)
#define ca(n, a) rp(ca_i, 0, n) cout << a[ca_i] << ((ca_i == n - 1) ? "\n" : " ")
#define za(n, a) rp(za_i, 0, n) a[za_i] = 0
#define be(a) a.begin(), a.end()
int main()
{
    ll n;
    cin >> n;
    cout << (n + 1) / 2 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>

typedef long long ll;

using namespace std;

int main() {
    int A, B, ans;

    cin >> A >> B;

    ans = A - 1;

    for (int i = B - ans; i <= B + ans; i++) {
        cout << i;
        cout << " ";
    }

    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define double long double
#define endre getchar();getchar();return 0
#define moder (int)(1e9+7)
#define inf (int)(5*1e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int kai(int x) {
	if (x == 0)return 1;
	return (kai(x - 1)*x) % moder;
}
int comb(int x, int y) {
	return kai(x)*mod_pow(kai(x - y), moder - 2, moder) % moder*mod_pow(kai(y), moder - 2, moder) % moder;
}
struct edge { int from, to, cost; };
int dx[5] = { 0,1,0,-1 }, dy[5] = { 1,0,-1,0 };
map<int, int>factor(int x) {
	map<int, int>res;
	for (int i = 2; i*i <= x; i++) {
		while (x%i == 0) {
			x /= i;
			res[i]++;
		}
	}
	if (x != 1)res[x]++;
	return res;
}
/*--------Library Zone!--------*/


signed main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << a * b - b * c - a * d + c * d << endl;
	endre;
}


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

// 比較関数
// --------------------------
typedef std::pair<int, int> mypair;
bool mycompare( const mypair &lhs, const mypair &rhs )
{
  if(lhs.second != rhs.second) {
    if (lhs.second < rhs.second) return lhs.second < rhs.second;
  }
  return lhs.first < rhs.first;
}

int main() {
  int N; cin >> N;
  map<string, int> odd;
  map<string, int> even;
  for(int i = 0; i < N; i++) {
    string a; cin >> a;
    if(i % 2 == 1) {
      if(odd.count(a) > 0) {
        odd.at(a)++;
      } else {
        odd[a] = 1;
      }
    } else {
      if(even.count(a) > 0) {
        even.at(a)++;
      } else {
        even[a] = 1;
      }
    }
  }

  pair<string,int> oddMaxV = make_pair("", 0);
  pair<string,int> oddMaxS = make_pair("", 0);
  for(auto o = odd.begin(); o != odd.end() ; ++o ) {
    if(oddMaxV.second <= o->second) {
      oddMaxS = oddMaxV;
      oddMaxV = make_pair(o->first, o->second);
    } else if(oddMaxS.second < o->second) {
      oddMaxS = make_pair(o->first, o->second);
    }
  }

  pair<string,int> evenMaxV = make_pair("", 0);
  pair<string,int> evenMaxS = make_pair("", 0);
  for(auto o = even.begin(); o != even.end() ; ++o ) {
    if(evenMaxV.second < o->second) {
      evenMaxS = evenMaxV;
      evenMaxV = make_pair(o->first, o->second);
    } else if(evenMaxS.second < o->second) {
      evenMaxS = make_pair(o->first, o->second);
    }
  }

  // cout << oddMaxV.first << ":" << oddMaxV.second << endl;
  // cout << oddMaxS.first << ":" << oddMaxS.second << endl;
  // cout << evenMaxV.first << ":" << evenMaxV.second << endl;
  // cout << evenMaxS.first << ":" << evenMaxS.second << endl;

  if(oddMaxV.first != evenMaxV.first) {
    cout << N - oddMaxV.second - evenMaxV.second << endl;
  } else {
    if( (oddMaxV.second - (oddMaxS.second) ) < (evenMaxV.second - (evenMaxS.second)) ) {
      cout << N - oddMaxS.second - evenMaxV.second << endl;
    } else {
      cout << N - oddMaxV.second - evenMaxS.second << endl;
    }
  }
}


Measured memory_bytes: 11264
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

#define gcu getchar_unlocked
#define pcu putchar_unlocked
#define _T template <typename T>
#define _HT template <typename H, typename... T>
#define _il inline
#define _in _il int in
#define _sc _il bool scan
_T T in(int c){T n=0;bool m=false;if(c=='-')m=true,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0');return m?-n:n;} //&&c<='9'
_in() {return in<int>(gcu());}
_T T scan(T &n){int c=gcu();return c==EOF?false:(n=in<T>(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_sc(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#endif
_HT _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _vo _il void out
#define _vl _il void outl
_vo(const char *s){while(*s)pcu(*s++);}
_vo(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_vo(string s){for(char c:s)pcu(c);}
#endif
_T _vo(T n){static char buf[20];char *p=buf;
	if(n<0)pcu('-'),n*=-1;if(!n)*p++='0';else while(n)*p++=n%10+'0',n/=10;
	while (p!=buf)pcu(*--p);}
_vl(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _vo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);outl();}
#endif
_HT _vo(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _vl(T&&... t){out(move(t)...);outl();}

void dump(int n) {
		out(n, ':');
		for (int j = 0, t; (t = n >> j); j++)
			if (t & 1)
				out(' ', j);
		outl();
}

typedef vector<int> v;
void enumeration(int t, int i, int n, v &r) {
	if (i >= n) {
		r.push_back(t);
		return;
	}

	if ((t >> i) & 1)
		enumeration(t, i + 1, n, r);
	else {
		enumeration(t, i + 1, n, r);
		enumeration((1 << i) | t, i + 1, n, r);
	}
}

int main() {
	int n = in(), u = 0;
	v r;
	for (int i = in(); i; i--)
		u |= 1 << in();
	enumeration(u, 0, n, r);
	sort(r.begin(), r.end());
	for (int x: r)
		dump(x);
}


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

namespace AtCoder.Abc
{
    class QuestionB
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 文字列の入力
            string T = Console.ReadLine();

            string p = T.Replace("?", "D");

            Console.WriteLine(p);
            Console.Out.Flush();
        }
    }
}



Measured memory_bytes: 28956
use std::str::FromStr;
use std::io::stdin;

fn main() {
    let n = read::<usize>();
    let mut dp: Vec<usize> = vec![123456; 1000000];
    dp[0] = 0;
    for i in 0..n+1 {
        let mut nine: usize = 9;
        let mut six: usize  = 6;
        while nine <= n+1 {
            dp[i+nine] = std::cmp::min(dp[i]+1, dp[i+nine]);
            nine *= 9;
        }
        while six <= n+1 {
            dp[i+six] = std::cmp::min(dp[i]+1, dp[i+six]);
            six *= 6;
        }
        dp[i+1] = std::cmp::min(dp[i]+1,dp[i+1]);
    }

    println!("{}", dp[n]);
}

fn read<T: FromStr>() -> T {
    let mut line = String::new();
    stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}
/*
fn read_vec<T: FromStr>() -> Vec<T> {
    let mut line: String = String::new();
    stdin().read_line(&mut line).ok();
    line.trim().split_whitespace()
        .map(|i| i.parse().ok().unwrap()).collect()
}
*/

Measured memory_bytes: 12540
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define REV(x) reverse(ALL(x))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ld = long double;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using Pll_ll = pair<ll, ll>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;
const double EPS = 1E-10;

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


int main(){
    int N; cin >> N;
    VS A(3);
    REP(i, 3) cin >> A[i];
    int cnt = 0;
    REP(i, N){
        set<char> cs;
        REP(j, 3)
            cs.insert(A[j][i]);
        cnt += cs.size() - 1;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
from itertools import accumulate

N, Q = map(int, input().split())
S = input()
List = [list(map(int, input().split())) for _ in range(Q)]

flg = []
for i in range(N-1):
    tmp_S = S[i:i+2]
    if tmp_S == "AC":
        flg.append(1)
    else:
        flg.append(0)

flg_2 = [0]+flg
flg_2 = list(accumulate(flg_2))

for j in range(Q):
    print(flg_2[List[j][1]-1]-flg_2[List[j][0]-1])

Measured memory_bytes: 33172
#include<stdio.h>
int main(void){
	int H[1000],W[1000];
	int n,h,w,k;

	for(n=0;;n++){
		scanf("%d %d",&H[n],&W[n]);
		if (H[n]==0 && W[n]==0 ) {
			break;
		}
	}

	for(k=0;k < n;k++){
		for (h = 0; h < H[k]; h++) {
			for (w = 0; w < W[k]; w++) {
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}

	return 0;
}



Measured memory_bytes: 1960
for i in range(int(input())):
    point = 0
    out = 0
    runner = [0, 0, 0]
    while True:
        event = input()
        if event == 'HIT':
            if runner[2] == 1:
                point += 1
                runner[2] = 0
            if runner[1] == 1:
                runner[2] = 1
                runner[1] = 0
            if runner[0] == 1:
                runner[1] = 1
            runner[0] = 1
        elif event == 'HOMERUN':
            point += (sum(runner)+1)
            runner = [0, 0, 0]
        elif event == 'OUT':
            out += 1
            if out == 3:
                print(point)
                break

Measured memory_bytes: 7708
n = int(input())
SP = []
for i in range(n):
    s, p = input().split()
    SP.append((s, int(p), i+1))
SP.sort(key=lambda x: x[1], reverse=True)
SP.sort(key=lambda x: x[0])
for s, p, i in SP:
    print(i)


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;

void solve(){
  int n, ans = 0; cin >> n;
  string s; cin >> s;
  vector<map<char, int> > v(n, map<char, int> {{'R', 0}, {'G', 0}, {'B', 0}});
  vector<int> r(n, 0), g(n, 0), b(n, 0);
  v[n - 1][s[n - 1]]++;
  for(int i = n - 2; i >= 0; i--){
    v[i]['R'] = v[i + 1]['R'];
    v[i]['G'] = v[i + 1]['G'];
    v[i]['B'] = v[i + 1]['B'];
    v[i][s[i]]++;
  }

  long long cnt = 0;
  for(int i = 0; i < n - 3; i++){
    char a = s[i], b, c;
    for(int j = i + 1; j < n - 1; j++){
      char b = s[j];
      if(b == a) continue;
      if(a == 'R'){
        if(b == 'G') c = 'B';
        else c = 'G';
      }
      else if(a == 'G'){
        if(b == 'R') c = 'B';
        else c = 'R';
      }
      else{
        if(b == 'R') c = 'G';
        else c = 'R';
      }
      int k = j - i + j;
      /*cout << i << " " << j << " " << k << endl;
      cout << a << " " << b << " " << c << endl;
      cout << v[j + 1][c] << endl;*/

      if(k < n && s[k] == c) cnt--;
      cnt += v[j + 1][c];
    }
  }
  cout << cnt << endl;
/*
  for(int i = 0; i < n; i++){
    cout << v[i]['R'] << " ";
  }
  cout << endl;
  for(int i = 0; i < n; i++){
    cout << v[i]['G'] << " ";
  }
  cout << endl;
  for(int i = 0; i < n; i++){
    cout << v[i]['B'] << " ";
  }
  cout << endl;
*/

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


Measured memory_bytes: 4220
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
//		String s = sc.next();
		String s = sc.next();
		String t = sc.next();
		int a = sc.nextInt();
		int b = sc.nextInt();
		String u = sc.next();

		if(u.equals(s)) {
			a -= 1;
		}else {
			b -= 1;
		}

		System.out.println(a+" "+b);



	}
}


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

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

    int N, Y;
    cin >> N >> Y;
    for(int i = 0; i <= N; i++){
        for(int j = 0; j <= N; j++){
            int k = N - i - j;
            if(k < 0) continue;
            if(i * 10000 + j * 5000 + k * 1000 == Y){
                cout << i << ' ' << j << ' ' << k << endl;
                return 0;
            }
        }
    }

    cout << -1 << ' ' << -1 << ' ' << -1 << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
prev = input().rstrip()
log = []
log.append(prev)
for _ in [0]*(N-1):
    now = input().rstrip()
    if prev[-1] != now[0] or now in log:
        print('No')
        break
    log.append(now)
    prev = now
else: print('Yes')

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

int main(){
    int N;
    string S;
    cin >> N >> S;
    int x = 0;
    int max = 0;

    for(int i = 0; i < N; i++){
        if(S.at(i) == 'I'){
            x++;
        }
        else{
            x--;
        }

        if(max < x){
            max = x;
        }
    }

    cout << max << endl;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
 using namespace std;
 typedef long long ll;
 #define rep(i, j, n) for(int i = j; i < (int)(n); i++)
 const ll MOD = 1000000007;
 const ll INF = 1LL << 60;

 int main() {
   ll N, W;
   cin >> N >> W;
   vector<vector<ll>> dp(N + 1, vector<ll>(W + 1, 0));
   vector<ll> w(N), v(N);
   rep(i, 0, N) cin >> w.at(i) >> v.at(i);

   for (int i = N - 1; i >= 0; i--) {
     for (int j = 0; j <= W; j++) {
       if (j < w.at(i)) dp.at(i).at(j) = dp.at(i + 1).at(j);
       else dp.at(i).at(j) = max(dp.at(i + 1).at(j), dp.at(i + 1).at(j - w.at(i)) + v.at(i));
     }
   }
   cout << dp.at(0).at(W) << endl;
 }


Measured memory_bytes: 80256
import itertools
import math

def solve():
  N = int(input())
  K = int(input())
  log_N = math.ceil(math.log10(N+1))
  digit_table = range(0,log_N)
  ret = 0
  for comb in itertools.combinations(digit_table, K):
    num = 0
    stack = [0]
    next_stack = []
    log_N
    if sum(9*(10**c) for c in comb) <= N: 
      ret += 9**K
      continue
    for c in comb:
      while stack:
        num_base = stack.pop()
        for d in range(1,10):
          num = num_base+d*10**c

          # print(num)
          if c == comb[-1]:
            if num <= N: 
              # print(num)
              ret += 1
          else:
            next_stack.append(num)

      stack = next_stack
      next_stack = []

  print(ret)
  
solve()

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

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

    long long ans = 2 * (x / 11);
    if (x % 11 != 0)
    {
        ans++;
        if (x % 11 > 6)
        {
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import sys

n,m=input().split()
N = int(n)
M = int(m)
X = input().split()
#MはXの要素の数
X = [int(x) for x in X]

X.sort()
if M == 1:
    print(0)
    sys.exit()
elif M < 1:
    sys.exit()

minus = [X[i]-X[i-1] for i in range(1,M)]
#print(minus)

minus.sort()
#print(minus)
sum_num = 0
if N < M:
    for i in range(M-N):
        sum_num += minus[i]
    print(sum_num)
elif N >= M:
    print(0)


Measured memory_bytes: 13832
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#a = list(map(int, input().split()))

n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc=[]
for i in range(m):
    temp=list(map(int, input().split()))
    bc.append(temp)

a.sort()

bc.sort(key=lambda x:x[1],reverse=True)
#print(a)
#print(bc)

now=0
for i in range(n):
    if(a[i] < bc[now][1]):
        a[i] = bc[now][1]
        bc[now][0] -= 1
    else:
        break
    if(bc[now][0]==0):
        now+=1
    if(now>=m):
        break
    
print(sum(a))
#print(a)

Measured memory_bytes: 81596
//Author : Prakhar Asaiya
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(ll i = a; i < b; ++i)
#define REPN(i,a,b) for(ll i = a; i <= b; ++i)
#define REPV(i,a,b) for(ll i = a; i >= b; --i)
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define with_tests int t; cin>>t; while(t--){ solve(); }
#define without_tests solve();
#define all(x) (x).begin(), (x).end()
#define ll long long
#define INF 100000000
#define ff first
#define ss second
const int M=1e9+7;
 
void solve()
{
	string s,t;
	cin>>s>>t;
	int m = s.length(), n = t.length();
	int ans = INT_MAX;
	REP(i,0,m-n+1)
	{
		int cnt = 0;
		REP(j,0,n)
		{
			if(t[j] != s[i+j])
			{
				++cnt;
			}
		}
		//db1(cnt);
		ans = min(ans, cnt);
	}
	cout<<ans<<"\n";
}
 
int main()
{/*
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#*/
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  //with_tests;
  without_tests;
  return 0;
}

Measured memory_bytes: 3652
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
const double PI = acos(-1);  // PI = 3.141593...

struct Dice {
    int up, front, right, left, back, down;
    Dice(int _up, int _front, int _right, int _left, int _back, int _down) 
    :up(_up), front(_front), right(_right), left(_left), back(_back), down(_down) 
    {}
    void east() {
        int tmp = this->up;
        this->up = this->left;
        this->left = this->down;
        this->down = this->right;
        this->right = tmp;
    }
    void west() {
        int tmp = this->up;
        this->up = this->right;
        this->right = this->down;
        this->down = this->left;
        this->left = tmp;
    }
    void south() {
        int tmp = this->up;
        this->up = this->back;
        this->back = this->down;
        this->down = this->front;
        this->front = tmp;
    }
    void north() {
        int tmp = this->up;
        this->up = this->front;
        this->front = this->down;
        this->down = this->back;
        this->back = tmp;
    }
    void toRight() {
        int tmp = this->front;
        this->front = this->left;
        this->left = this->back;
        this->back = this->right;
        this->right = tmp;
    }
    void print() {
        printf("up: %d, down: %d, front: %d, back: %d, left: %d, right: %d\n"
        , this->up, this->down, this->front, this->back, this->left, this->right);
    }
    bool operator == (Dice& dice) {
        if(this->up == dice.up
        && this->down == dice.down
        && this->front == dice.front
        && this->back == dice.back
        && this->left == dice.left
        && this->right == dice.right) return true;
        else return false;
    }
};

int main() {
    int up, front, right, left, back, down;
    cin >> up >> front >> right >> left >> back >> down;
    Dice dice1(up, front, right, left, back, down);
    cin >> up >> front >> right >> left >> back >> down;
    Dice dice2(up, front, right, left, back, down);
    if(dice1 == dice2) {
        cout << "Yes" << endl;
        return 0;
    }
    if(dice1.up == dice2.left) dice2.east();
    if(dice1.up == dice2.right) dice2.west();
    if(dice1.up == dice2.front) dice2.north();
    if(dice1.up == dice2.back) dice2.south();
    if(dice1.up == dice2.down) {
        dice2.south();
        dice2.south();
    }
    for(int i = 0; i < 4; ++i) {
        dice2.toRight();
        if(dice1 == dice2) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3096
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define rep2(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
template<typename T> void read(T &num){
	char c=getchar();T f=1;num=0;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	num*=f;
}
template<typename T> void qwq(T x){
	if(x>9)qwq(x/10);
	putchar(x%10+'0');
}
template<typename T> void write(T x){
	if(x<0){x=-x;putchar('-');}
	qwq(x);putchar('\n');
}
long long co[100010];long long mx[100010];

int main(){
	int n;read(n);
	rep(i,0,n)read(co[i]);
	
	if(n==0){write((co[0]==1)?1:-1);}
	else{
		if(co[0]){write(-1);return 0;}
		mx[0]=1;
		rep(i,1,n-1){
			mx[i]=mx[i-1]*2-co[i];
			if(mx[i]>400000000000000000)mx[i]=400000000000000000;
			if(mx[i]<1){write(-1);return 0;}
		}
		
		long long now=co[n];long long ans=co[n];
		rep2(i,n-1,0){
			if(now>mx[i]*2){write(-1);return 0;}
			now=min(now,mx[i]);now+=co[i];ans+=now;	
		}
		write(ans);
	}
	return 0;
}

Measured memory_bytes: 5076
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
auto fl = [](auto a, auto b) { assert(b != 0); return a / b - (a % b != 0 && ((a >= 0) != (b >= 0)) ? 1 : 0); };
auto ce = [](auto a, auto b) { assert(b != 0); return a / b + (a % b != 0 && ((a >= 0) == (b >= 0)) ? 1 : 0); };
auto mo = [](auto a, auto b) { assert(b != 0); a %= b; if(a < 0) { a += abs(b); } return a; };
LL gcd(LL a, LL b) { return (b == 0 ? a : gcd(b, a % b)); }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)

// ---- ----

int main() {
	int k, x;
	cin >> k >> x;
	
	cout << (k * 500 >= x ? "Yes" : "No") << endl;
	
	return 0;
}


Measured memory_bytes: 256
using System;
using System.IO.Pipes;

class SheepAndWolf
{
    static void Main(string[] args)
    {
        var ans = "safe";


        var input = Console.ReadLine().Split(' ');

        if(int.Parse(input[0]) <= int.Parse(input[1]))
        {
            ans = "unsafe";
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 17832
import sys
def input(): return sys.stdin.readline().strip()
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
c=0
for i in range(n):
    l[n-1-i][0]+=c
    c+=-l[n-1-i][0]%l[n-1-i][1]
print(c)

Measured memory_bytes: 31348
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<cmath>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 3;
int a[N];
int n;
int top;
int sum[N];
int f[N];
int R[N];
inline int read(){
	int v = 0,c = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') c = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		v = v * 10 + ch - 48;
		ch = getchar();
	}
	return v * c;
}
int ans;
int main(){
	n = read();
	for(int i = 1;i <= n;++i) a[i] = read();
//	for(int i = n;i >= 1;--i){
//		while(top && a[s[top]] <= a[i]) top--;
//		R[i] = top ? s[top] : n + 1;
//		s[++top] = i;	
//	}
//	for(int i = 1;i <= n;++i) sum[i] = a[i] - a[i - 1] <= 0 ? 0 : 1;
	a[0] = 2000000000;
	f[0] = -1;
	for(int i = 1;i <= n;++i){
		f[i] = a[i] <= a[i - 1] ? f[i - 1] + 1 : 0;	
		ans = max(ans,f[i]);
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 1024
# gets.chomp
# gets.chomp.to_i
# gets.chomp.split
# gets.chomp.split.map(&:to_i)

def max(a, b)
  a > b ? a : b
end

n, W = gets.chomp.split.map(&:to_i)
dp = Array.new(W + 1) { -1 }
dp[0] = 0
w = [] * n
v = [] * n
n.times do
  wi, vi = gets.chomp.split.map(&:to_i)
  w << wi
  v << vi
end

w.each.with_index do |wi, i|
  (W-wi).downto(0) do |j|
    next if dp[j] == -1

    dp[j + wi] = max(dp[j + wi], dp[j] + v[i])
  end
end

puts dp.max

Measured memory_bytes: 2556
Scanf.scanf "%d" (fun n ->
    let a = Array.make (n + 1) 0 in
    let b = Array.make (n + 1) 0 in
    let bb = Array.make n 0 in
    let module S = Set.Make (struct type t = int * int let compare = compare end) in
    for i = 1 to n do Scanf.scanf " %d" (fun j -> a.(j) <- a.(j) + 1) done;
    for i = 1 to n do Scanf.scanf " %d" (fun j -> b.(j) <- b.(j) + 1; bb.(i - 1) <- j) done;

    let rec check i =
        if i > n then true else if a.(i) + b.(i) > n then false else check (i + 1)
    in
    if check 1 then (
        let c = Array.make (n + 1) 0 in
        let d = Array.make (n + 1) 0 in
        for i = 1 to n do
            c.(i) <- c.(i - 1) + a.(i);
            d.(i) <- d.(i - 1) + b.(i);
        done;
        let rec loop i mx =
            if i > n then mx else loop (i + 1) (max mx (c.(i) - d.(i - 1)))
        in
        let x = loop 1 0 in
        print_endline "Yes";
        for i = 0 to n - 1 do
            Printf.printf "%d " bb.((i - x + n) mod n)
        done;
        print_newline ()
    ) else print_endline "No"
)

Measured memory_bytes: 14104
# 素因数分解によってx=p**n+q**m+...と表せるとき、
# 約数の個数は(n+1)*(m+1)*...
# つまり、約数が75個(素因数分解すると3*5*5)あるというのは素数が
# [2, 4, 4]個ずつor[4, 14]個ずつor[2, 24]個ずつor[74]個ある組み合わせを数えればよい

from collections import Counter, defaultdict
from itertools import product

n = int(input())

def prime_factorization(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

prime = []
for i in range(1, n+1):
    prime += prime_factorization(i)
    
ctr = Counter(prime)

# 各素数が[2, 4, 14, 24, 74]個以上ある素数を求める
d = defaultdict(list)
for k, v in ctr.items():
    for p in [2, 4, 14, 24, 74]:
        if v >= p:
            d[p].append(k)
        else:
            break

            
# 組み合わせ(重複している組みあわせはcontiue)
comb_num = 0
for comb in [[2, 4, 4], [4, 14], [2, 24], [74]]:
    for prime_comb in list(product(*[d[c] for c in comb])):
        if len(prime_comb) != len(set(prime_comb)):
            continue
        if comb == [2, 4, 4] and prime_comb[1] < prime_comb[2]:
            continue
        comb_num += 1
print(comb_num)            

Measured memory_bytes: 3444
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		sc.close();
		if(a < b) {
			System.out.println("a < b");
			return;
		} else if (a == b) {
			System.out.println("a == b");
			return;
		} else {
			System.out.println("a > b");
		}
	}
}


Measured memory_bytes: 26236
m = int(input())
L = []
for _ in range(m):
    L.append(list(map(int, input().split())))

short = []
additional = 0
for elm in L:
    additional += (elm[1] - 1)
    total = elm[0] * elm[1]
    if total > 9:
        if total % 9 == 0:
            additional += (total // 9) - 1
        else:
            additional += total // 9
        # additional += (total - 1) // 9
    if total > 9:
        if total % 9 == 0:
            res = 9
        else:
            res = total % 9
    else:
        res = total
    short.append(res)

prev = 0
additional += len(short) - 1
for elm in short:
    prev = prev + elm
    if prev > 9:
        prev -= 9
        additional += 1

print(additional)



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

template <typename T>
struct graph {

	struct edge {
		int from, to;
		T cost;
	};

	vector<edge> edges;
	vector<vector<int>> g;
	int n;

	graph(int n) : n(n) {
		g.resize(n);
	}

	virtual void add(int from, int to, T cost) = 0;
};

template <typename T>
struct undirected_graph : graph<T> {
	using graph<T>::edges;
	using graph<T>::g;
	using graph<T>::n;

	undirected_graph(int n) : graph<T>(n) {
	}

	void add(int from, int to, T cost = 1) {
		assert(0 <= from && from < n && 0 <= to && to < n);
		g[from].emplace_back(edges.size());
		g[to].emplace_back(edges.size());
		edges.push_back({from, to, cost});
	}
};

template <typename T>
vector<T> dijkstra(const graph<T> &g, int start){
	assert(0 <= start && start < g.n);
	vector<T> dist(g.n, numeric_limits<T>::max());
	priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> s;
	dist[start] = 0;
	s.emplace(dist[start], start);
	while (!s.empty()) {
		int expected = s.top().first;
		int i = s.top().second;
		s.pop();
		if (dist[i] != expected) {
			continue;
		}
		for (int id : g.g[i]) {
			auto &e = g.edges[id];
			int to = e.from ^ e.to ^ i;
			if (dist[i] + e.cost < dist[to]) {
				dist[to] = dist[i] + e.cost;
				s.emplace(dist[to], to);
			}
		}
	}
	return dist;
}

int main(){
	int64_t n, m;
	cin >> n >> m;
	undirected_graph<int> g(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g.add(a, b);
	}
	vector<int> d = dijkstra(g, 0);
	bool f = true;
	for (auto &e : g.edges) {
		if (d[e.from] % 2 == d[e.to] % 2) {
			f = false;
			break;
		}
	}
	if (f) {
		int64_t a = 0;
		for (int i = 0; i < n; i++) {
			a += d[i] % 2;
		}
		int64_t b = n - a;
		cout << a * b - m << endl;
	} else {
		cout << n * (n - 1) / 2 - m << endl;
	}
	return 0;
}

Measured memory_bytes: 8116
#include <stdio.h>
#include <stdlib.h>
int c(const void *v1,const void *v2){
    return *(int *)v1-*(int *)v2;
}
 
int main(void){
    int i,n,line[10000];
    long long sum;
    for(;sum=0,~scanf("%d",&n);){
        for(i=0;i<n;i++)
            scanf("%d",&line[i]);
        qsort(line,n,sizeof(int),c);
        for(i=0;i<n;i++){
            sum+=line[i]*(n-i);
        }
        printf("%lld\n",sum);
    }
    return 0;
}

Measured memory_bytes: 612
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#include <cmath>
#include <limits>
using namespace std;

int getDegit(long num) {
	long digit = 0;
	while (num != 0) {
		num /= 10;
		digit++;
	}
	return digit;
}
int main() {
	//入力
	long N = 0;
	cin >> N;
	//cout << N << endl;
	long AB = 0;

	//処理
	for (long i = sqrt(N); i > 0; i--) {
		if (N % i == 0) {
			AB = N / i;
			break;
		}
	}
	//cout << AB << endl;
	//桁数え
	long ans = 0;
	ans = getDegit(AB);
	//出力
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cstdlib>
#define rep(i,x) for(int i=0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 10010010010;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
ll gcd(ll a, ll b) {//a>b
    if (a < b)swap(a, b);
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}

int main() {
    ll N, M;
    cin >> N >> M;//switch n light m
    vector<vector<ll>> num(M,vector<ll>(12));
    vector<ll> light(M);
    vector<ll> amari(M);
    rep(i, M) {
        cin >> light[i];
        rep(j, light[i]) {
            cin >> num[i][j];
        }
    }
    ll ans = 0;
    rep(i, M)cin >> amari[i];
    for (int i = 0; i < (1 << N); i++) {
        vector<bool> now(N, false);
        for (int j = 0; j < N; j++) {
            if ((i >> j) & 1) {
                now[j] = true;
            }
        }
        bool ok = true;
        rep(j, M) {
            ll cnt = 0;
            rep(k, light[j]) {
                if (now[num[j][k] - 1] == true)cnt++;
            }
            if (cnt % 2 != amari[j])ok = false;
        }
        if (ok) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// Hey! 僕の提出を見てくれてありがとう.
// ロボ子さん可愛いぞ！！！！！君もV沼にはまろう↓
// https://www.youtube.com/channel/UCDqI2jOz0weumE8s7paEk6g
using namespace std;
/*
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
namespace mp = boost::multiprecision;// 任意長整数型
using bint = mp::cpp_int;// 仮数部長が32の浮動小数点数型
using real32 = mp::number<mp::cpp_dec_float<32>>;// 仮数部長が1024の浮動小数点数型
using real1024 = mp::number<mp::cpp_dec_float<1024>>;// ついでに有理数型
using rat = boost::rational<bint>;
*/
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示
//sortを降順にする時は greater<型>()
ll a,b;
int main(){ //srand((unsigned)time(NULL));
  cin >> a >> b;
  if(a==b){
    cout << "a == b" << endl;
  }else if(a < b){
    cout << "a < b" << endl;
  }else{
    cout << "a > b" << endl;
  }
}



Measured memory_bytes: 3108
from heapq import heappush, heappop, heappushpop, heapreplace, heapify

n, e, k= map(int, input().split())


#edge_listに各辺の情報を格納する
#無向ver
edge_list = [[] for i in range(n)]
for _ in range(e):
    s, t, u = map(int, input().split())
    edge_list[s].append([u, t])

    #これは、グラフの入力方法によって必要かどうか変わってくるので注意！！！(有向グラフの場合いらない）
    #edge_list[t].append([u, s])


#隣接行列及びスタートを与えると、各頂点までの最短経路を算出するダイクストラ関数
def dijkstra(edges, start):
    #startの点から各頂点までの最短距離
    d = [float("inf")] * n
    used = [False] * n
    d[start] = 0
    used[start] = True
    #各ノードへのstartからのcostを記録するlistを導入
    node_cost_list = []

    for e in edges[start]:
        heappush(node_cost_list, e)
    while len(node_cost_list):
        min_cost_node = heappop(node_cost_list)
        if used[min_cost_node[1]]:
            continue
        v = min_cost_node[1]
        d[v] = min_cost_node[0]
        used[v] = True
        for z in edges[v]:
            if not used[z[1]]:
                heappush(node_cost_list, [z[0]+d[v], z[1]])
    return d


if __name__ == "__main__":
    for i in dijkstra(edge_list,k):
        if i == float("inf"):
            print("INF")
        else:
            print(i)


'''
4 6 1
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5
'''



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

int main(void)
{
    intmax_t N, A, B;
    intmax_t ans = 0;

    scanf("%jd%jd%jd", &N, &A, &B);

    if ((llabs(A - B) % 2) == 0) {
        ans = llabs(A - B) / 2;
    } else {
        intmax_t max = A > B ? A : B;
        intmax_t min = A < B ? A : B;
        intmax_t ans1, ans2;
        ans1 = min + (llabs(A - B) / 2);
        ans2 = (N - max + 1) + (llabs(A - B) / 2);
        ans = ans1 < ans2 ? ans1 : ans2;
    }

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

    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

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

	unordered_map<string, int> map;
	long long result = 0;
	for(int i = 0; i < N; i++) {
		string s;
		cin >> s;
		sort(s.begin(), s.end());

		result += map[s];
		map[s]++;
	}

	cout << result << endl;

	return 0;
}


Measured memory_bytes: 10660