akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<pair<int, int>>> g;
vector<int> color;

void input_build() {
	// 入力からグラフの生成
	cin >> n; g.resize(n);
	color.resize(n - 1);
	for (int i = 0; i < n - 1; ++i) {
		int a, b; cin >> a >> b;
		--a; --b;
		g[a].emplace_back(b, i);
		g[b].emplace_back(a, i);
	}
}

void solve(int s, int prv = 0) {
	static vector<bool> visited(n, false);
	visited[s] = true;
	int c = prv != 1 ? 1 : 2;
	for (auto e : g[s]) {
		int nx = e.first;
		if (visited[nx]) continue;
		color[e.second] = c;
		solve(nx, c);
		c = c + 1 == prv ? prv + 1 : c + 1;
	}
}

signed main() {
	input_build();
	solve(0);
	cout << *max_element(color.begin(), color.end()) << endl;
	for (auto c : color)
		cout << c << endl;
	return 0;
}

Measured memory_bytes: 6912
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>

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

using namespace std;

void solve(string s1, string s2) {
    vector<vector<int> > dp(s1.size()+1, vector<int>(s2.size()+1,0));
    rep(i, s1.size()+1) {
        rep(j, s2.size()+1) {
            if(i == 0 || j == 0)
                continue;
            if(s1[i-1] == s2[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    cout << dp[s1.size()][s2.size()] << endl;
    return;
}

int main(){
    int n; cin >> n;
    string s1,s2;
    rep(i, n) {
        cin >> s1 >> s2;
        solve(s1,s2);
    }
}




Measured memory_bytes: 6812
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define DBG(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
const ll p = 1e9+7;
const ll INF = 1LL << 60;

vector<int> g[111111];
int pc[111111];
int df[111111];

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=1;i<n+m;i++){
    int a,b;
    cin>>a>>b;
    pc[b]++;
    g[a].PB(b);
  }
  int root;
  for(int i=1;i<=n;i++){
    if(pc[i]==0)root=i;
  }
  //  DBG(root);
  queue<P> q;
  int cnt[111111]={};
  q.push(MP(root,0));
  
  while(q.size()){
    P p=q.front();
    q.pop();
    cnt[p.F]++;
    if(cnt[p.F]==pc[p.F]||p.F==root){
	 df[p.F]=p.S;
	 for(int i=0;i<g[p.F].size();i++)
	   q.push(MP(g[p.F][i],p.S+1));
    }
  }

  
  int ans[111111]={};
  for(int i=1;i<=n;i++){
    for(int j=0;j<g[i].size();j++){
	 if(df[i]+1==df[g[i][j]])ans[g[i][j]]=i;
    }
  }
  for(int i=1;i<=n;i++){
    cout<<ans[i]<<endl;
  }
 
  return 0;
}


Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> x(100010,vector<int>(3)),dp(100010,vector<int>(4,-1));
int n;

int ans(int curr , int last){
    if(curr == n){
        return 0;
    }
    if(dp[curr][last] != -1){
        return dp[curr][last];
    }
    int ret = 0;
    for(int i = 0 ; i < 3 ; i += 1){
        if(i != last){
            ret = max(ret , x[curr][i] + ans(curr+1,i));
        }
    }
    dp[curr][last] = ret;
    return ret;
}

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i += 1){
        cin >> x[i][0] >> x[i][1] >> x[i][2];
    }
    cout << ans(0,3);
}

Measured memory_bytes: 18944
#include <stdio.h>

int main(void){
  
  int A1;
  int A2;
  int A3;
  
  scanf("%d %d %d",&A1,&A2,&A3);

  
  
  if(A1 <= A2 && A2 <= A3){
    printf("%d",(A2 - A1) + (A3 - A2));
  }
  else if(A1 <= A3 && A3 <= A2){
    printf("%d",(A3 - A1) + (A2 - A3));
  }
  else if(A2 <= A1 && A1 <= A3){
    printf("%d",(A1 - A2) + (A3 - A1));
  }
  else if(A2 <= A3 && A3 <= A1){
    printf("%d",(A3 - A2) + (A1 - A3));
  }
  else if(A3 <= A1 && A1 <= A2){
    printf("%d",(A1 - A3) + (A2 - A1));
  }
  else{
    printf("%d",(A2 - A3) + (A1 - A2));
  }
  return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

int d[30][30];
int cnt[3][30];
ll s[3][30];

void solve()
{
    int N, n;
    scanf("%d%d", &N, &n);
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &d[i][j]);
        }
    }

    /*for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);*/

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            int c;
            scanf("%d", &c); c--;
            int k = (i + j) % 3;
            cnt[k][c]++;
        }
    }
    ll ans = LINF;
    for (i = 0; i < 3; i++) {
        int k;        
        for (k = 0; k < n; k++) {
            for (j = 0; j < n; j++) {
                s[i][k] += (ll)d[j][k] * cnt[i][j];
            }
        }
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (i == j) continue;
            int k;
            for (k = 0; k < n; k++) {
                if (k == i || k == j) continue;
                ll tmp=s[0][i] + s[1][j] + s[2][k];
                ans = MIN(ans, tmp);
            }
        } 
    }

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

    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T; scanf("%d", &T);
    while(T--) {
        solve();
    }
#endif
    return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a;
	int ans = 0, r = 9;
	bool zero = true;
	rep(i,5){
		cin >> a;
		if(a%10 != 0) zero = false;
		if(a%10 != 0) chmin(r, a%10);
		if(a%10 != 0) a = ((a+10)/10)*10;
		ans += a;
	}
	if(!zero) ans -= 10 - r;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline int_fast64_t read(){int_fast64_t x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
void Main() {
    read();
    int K = read(), i = 1, ans = 0;
    vector<int> V;
    V.push_back(0);
    char c = getchar();
    while(c != '0' && c != '1'){
        c = getchar();
    }
    while(c == '0' || c == '1'){
        V.push_back(V[i-1]);
        while (c == '1'){
            V[i]++;
            c = getchar();
        }
        i++;
        V.push_back(V[i-1]);
        while (c == '0'){
            V[i]++;
            c = getchar();
        }
        i++;
    }
    int Vsize = V.size();
    for(int j = 1; j<Vsize; j += 2) ans = max(ans, V[min(j+2*K, Vsize-1)]-V[j-1]);
    printf("%d\n", ans);
}
int main(){cin.tie(nullptr);ios::sync_with_stdio(false);Main();return 0;}


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

typedef long long ll;
const int N = 1010;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct edge
{
    int to, cost, next;
}g[N*10];
int cnt, head[N];
int num[N];
ll dis[N];
bool vis[N];
void add_edge(int v, int u, int cost)
{
    g[cnt].to = u, g[cnt].cost = cost, g[cnt].next = head[v], head[v] = cnt++;
}
void spfa(int s, int t, int n)
{
    queue<int> que;
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    memset(num, 0, sizeof num);
    que.push(s), dis[s] = 0, vis[s] = true, num[s]++;
    bool flag = false;
    while(! que.empty())
    {
        int v = que.front(); que.pop();
        vis[v] = false;
        for(int i = head[v]; i != -1; i = g[i].next)
        {
            int u = g[i].to;
            if(dis[u] > dis[v] + g[i].cost)
            {
                dis[u] = dis[v] + g[i].cost;
                if(! vis[u])
                {
                    vis[u] = true, que.push(u);
                    num[u]++;
                    if(num[u] > n && num[t] > n)
                    {
                        printf("inf\n"); return;
                    }
                    if(num[u] > 2*n)
                    {
                        flag = true; break;
                    }
                }
            }
        }
        if(flag) break;
    }
    printf("%lld\n", -dis[t]);
}
int main()
{
    int n, m, a, b, c;
    scanf("%d%d", &n, &m);
    cnt = 0;
    memset(head, -1, sizeof head);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        add_edge(a, b, -c);
    }
    spfa(1, n, n);
    return 0;
}


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

int main() {
  int n,m;
  int a[40][2]={};
  int tmp;
  int tmp2;
  int kazu=0;
  bool ok=true;
  cin >> n >> m;
  cin >> tmp;
  for(int j=0;j!=tmp;j++){
    cin >> tmp2;
    a[j][0]=tmp2;
    kazu++;
  }
  for(int i=0;i!=n-1;i++){
    cin >> tmp;
    for(int j=0;j!=tmp;j++){
      cin >> tmp2;
      for(int x=0;x<kazu;x++){
        if(a[x][0]==tmp2){
          a[x][1]++;
        }
      }
    }
  }
  int ans=0;
  for(int i=0;i!=kazu;i++){
    if(a[i][1]==n-1){
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define max_weight 10000007
int dp[max_weight];
int w[104], v[104];
signed main()
{
    int n, W;
    cin >> n >> W;
    for (int i = 0; i < n; i++)
        cin >> w[i] >> v[i];
    for (int i = 0; i < max_weight; i++)
        dp[i] = 0;
    for (int i = 0; i < n; i++)
        for (int j = W - w[i]; j >= 0; j--)
            if (dp[j + w[i]] < dp[j] + v[i])
                dp[j + w[i]] = dp[j] + v[i];
    cout << dp[W];
}

Measured memory_bytes: 78464
n=int(input())
a=int(n/1.08)
aa=a-1
aaa=a+1
b=int(a*1.08)
bb=int(aa*1.08)
bbb=int(aaa*1.08)
A=[a,aa,aaa]
B=[b,bb,bbb]
f=0
for i in range(3):
  if B[i]==n:
    f=1
    ans=A[i]
    break
if f==0:
  print(":(")
else:
  print(ans)

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

int main(){
  int n,i,j;
  string s;
  cin >> n;
  cin >> s;
  int a[n];
  bool flag;
  for(j=0;j<=3;j++){
    a[0]=j%2;
    a[1]=j/2;
    flag = false;
    for(i=1;i<n-1;i++){
      if(a[i]==1){
        if(s[i]=='o')a[i+1]=a[i-1];
        else a[i+1]=1^a[i-1];
      }else{
        if(s[i]=='o')a[i+1]=1^a[i-1];
        else a[i+1]=a[i-1];
      }
    }

    if(a[n-1]==1){
      if(s[n-1]=='o' && a[0]==a[n-2])flag = true;
      else if(s[n-1]=='x' && a[0]!=a[n-2])flag = true;
    }else{
      if(s[n-1]=='o' && a[0]!=a[n-2])flag = true;
      else if(s[n-1]=='x' && a[0]==a[n-2])flag = true;
    }
    bool f2=false;
    if(a[0]==1){
      if(s[0]=='o' && a[1]==a[n-1])f2 = true;
      else if(s[0]=='x' && a[1]!=a[n-1])f2=true;
    }else{
      if(s[0]=='o' && a[1]!=a[n-1])f2 = true;
      else if(s[0]=='x' && a[1]==a[n-1])f2=true;
    }
    if(flag && f2){
      for(i=0;i<n;i++){
        if(a[i]==1)cout << 'S';
        else cout << 'W';
      }
      cout << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}


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

int main() {
  double a, b, h, m;
  cin >> a >> b >> h >> m;
  double x;
  double y;
  double pi = 3.1415926535897932;
  x = 60 * h + m;
  y = a*a + b*b - 2*a*b*cos(pi*x/360 - pi*x/30);
  double z;
  z = sqrt(y);
  cout << setprecision(12) << z << endl;
}

Measured memory_bytes: 4248
#include<bits/stdc++.h>
using namespace std;
auto no = [](){cout << "NO"; exit(0);};
auto read = [](){int x; cin >> x; return x;};
int main(){
	ios::sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	if((N + 1) / 2 < K) no();
	cout << "YES";
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int cur,p,q,r;
string s;

int form(){
	if(isdigit(s[cur]))return s[cur++]-'0';
	if(s[cur]=='P'){cur++;return p;}
	if(s[cur]=='Q'){cur++;return q;}
	if(s[cur]=='R'){cur++;return r;}
	if(s[cur]=='-'){cur++;return 2-form();}
	if(s[cur]=='('){
		cur++;
		int a=form();
		char op=s[cur++];
		int b=form();
		if(op=='+')a=max(a,b);
		else a=min(a,b);
		assert(s[cur]==')');
		cur++;
		return a;
	}
} 

int main() {
	while(cin>>s){
		if(s==".")return 0;
		int ans=0;
		for(int i=0;i<27;i++){
			p=i/9;q=(i/3)%3;r=i%3;
			cur=0;
			if(form()==2)ans++;
		}
		cout<<ans<<endl;
	}
} 

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

int main()
{
  int n; cin >> n;
  set<char> s;
  rep(i, n){
    char c; cin >> c;
    s.insert(c);
  }
  if(s.size() == 3) cout << "Three" << endl;
  else cout << "Four" << endl;
  system("pause");
}


Measured memory_bytes: 504
from collections import deque
inf = float('inf')
around = [[0,1],[1,0],[0,-1],[-1,0]]

H,W = map(int,input().split())
A = [list(input()) for _ in range(H)]

dq = deque()

for i,line in enumerate(A):
    for j,e in enumerate(line):
        if e == "#":
            dq.append([i,j,0])

def bfs():
    res = 0
    while dq:
        i,j,d = dq.popleft()
        d += 1
        for di,dj in around:
            ni = i + di; nj = j + dj
            if not(0 <= ni <= H-1 and 0 <= nj <= W-1):
                continue
            if A[ni][nj] == ".":
                A[ni][nj] = "#"
                dq.append([ni,nj,d])
                if d > res:
                    res = d
    return res

ans = bfs()
print(ans)

Measured memory_bytes: 169052
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

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

using namespace std;

int main() {
  int n,t;
  cin>>n>>t;
  vector<int> a(n);
  REP(i,n)cin>>a[i];
  sort(begin(a),end(a));
  int64_t res = 1;
  REP(i,n) {
    int j=lower_bound(begin(a),end(a),a[i]-t)-begin(a);
    res *= i-j+1;
    res %= 1000000007;
  }
  cout<<res<<endl;
  return 0;
}

Measured memory_bytes: 1524
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n, m; cin >> n >> m;
    vector<ll> wa(n, 0), ac(n, 0);
    ll a = 0, w = 0;
    for(int i=0; i<m; ++i){
        int p; string s;
        cin >> p >> s ; p--;
        if(s=="AC"){
            if(!ac[p]){
                a++; ac[p] = 1;
                w += wa[p];
            }
        }else{
            wa[p]++;
        }
    }
    cout << a << ' ' << w << endl;
    return 0;
}

Measured memory_bytes: 4844
def prime(n):
    nums = [True]*n
    primes = []
    for i in range(2,n):
        if nums[i]:
            primes.append(i)
            for j in range(2*i,n,i):
                nums[j] = False
    return primes

def main():
    n = int(input())
    Alist = list(map(int,input().split()))
    A = set(Alist)

    Amax = max(A)
    primes = set(prime(Amax+1))
    ct = 1
    if (1 not in A and len(A) != n) or (1 in A and len(A)-1 != n-Alist.count(1)):
        ct = 2
    for p in primes:
        g = set(())
        temp = p
        while temp <= Amax:
            g.add(temp)
            temp+=p
        
        k = len(g & A)
        if k > ct:
            ct = k
    

    if (1 not in A) and (len(A)==1 or ct == len(A)):
        print("not coprime")
    elif ct == 1 or A=={1}:
        print("pairwise coprime")
    else:
        print("setwise coprime")
main()

Measured memory_bytes: 251604
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <fstream>
#include <iomanip>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

template<class T> T maximum(T head, T tail) { return std::max(head, tail); }
template<class H, class... T> H maximum(H head, T... tail) { return std::max(head, maximum(tail...)); }

template<class T> T minimum(T head, T tail) { return std::min(head, tail); }
template<class H, class... T> H minimum(H head, T... tail) { return std::min(head, minimum(tail...)); }

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  ll i = 0;
  for (auto x : v) {os << " [" << i++ << "]" << x; if (i % 10 == 0) os << std::endl;}
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::vector< std::pair<T, S> > vp)
{
  ll i = 0;
  for (auto p : vp) {os << " [" << i++ << "]" << p.first << " " << p.second; if (i % 10 == 0) os << std::endl;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

  std::string s;
  std::cin >> s;

  std::map<char, ll> mc;
  mc['C'] = -1;
  mc['F'] = -1;
  for (ll i = 0; i < (ll)s.size(); i++) {
    mc[s[i]] = i;
  }

  std::string judge = (mc['C'] >= 0 && mc['F'] >= 0 && mc['C'] < mc['F']) ? "Yes" : "No";

  print(judge);
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define for1(i, n) for (int i = 1; i <= n; ++i)
#define for0(i, n) for (int i = 0; i < n; ++i)
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()

#define next qwerty1
#define left qwerty2
#define right qwerty3
#define y1 qwerty4
#define y0 qwerty5

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;







int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d\n", max({a + b, a - b, a * b}));
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;


void solve(long long S, long long W){
    if( S <= W) {
        cout << "unsafe" << endl;
    }else {
        cout << "safe" << endl;
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long S;
    scanf("%lld",&S);
    long long W;
    scanf("%lld",&W);
    solve(S, W);
    return 0;
}


Measured memory_bytes: 3760
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority_queue
#include<deque>//double_ended queue
using namespace std;
typedef pair<int,int> P;//Pでpair<-,->を表す。
typedef long long LL; 
LL MOD=1000000007;

int main()
{ 
    LL l,r;
    cin>>l>>r;
    while(r>l+4038){r=r-2019;}
    LL min=2019;
    for(LL i=l;i<r;i++){
        for(LL j=i+1;j<=r;j++){
            if(((i*j)%2019)<min){min=((i*j)%2019);}
            if(min==0){break;}
        }
        if(min==0){break;}
    }
    cout<<min<<endl;
    return 0;
}

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

using namespace std;

int n, m;
vector<int> par, a, b;

int find(int x) {
  return par[x] == x ? x : par[x] = find(par[x]);
}

void unite(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) return;
  par[y] = x;
}

bool solve(int id) {
  par.resize(n);
  for (int i = 0; i < n; i++) {
    par[i] = i;
  }
  for (int i = 0; i < m; i++) {
    if (i == id) continue;
    unite(a[i], b[i]);
  }
  set<int> st;
  for (int i = 0; i < n; i++) {
    st.insert(find(i));
  }
  return st.size() == 1;
}

int main(void) {
  cin >> n >> m;
  a.resize(m);
  b.resize(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
  }

  int ans = m;
  for (int i = 0; i < m; i++) {
    ans -= solve(i);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
/**
 *	author: abhiy13
 *	created: 07.01.2019 12:16:03
**/
#include <bits/stdc++.h>

using namespace std;

const long long inf = (long long)(1e15);

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> ar(N);
  for(int &x : ar) {
    cin >> x;
  }
  vector<long long> dp(N, inf);
  dp[0] = 0;
  for(int i = 0; i < N; ++i) {
    for(int j = 1; j <= 2; ++j) {
      if(i - j >= 0) {
        dp[i] = min(dp[i], dp[i - j] + abs(ar[i - j] - ar[i]));
      }
    }
  }
  cout << dp[N - 1] << '\n';
  return 0;
}

Measured memory_bytes: 1408
N, K = map(int, input().split())
S = input()
s = [int(S[i]) for i in range(0,N)]
#print (s)

ll = []
v = s[0]
a = 0
for i in range(0,N) :
    if s[i] == v :
        if s[i] == 1 :
            a += 1
        else :
            a -= 1
    else :
        ll.append(a)
        a = 0
        v = s[i]
        if s[i] == 1 :
            a += 1
        else :
            a -= 1
ll.append(a)    
#print (ll)

left = 0
right = 0
NN = len(ll)
max = 0
ln = 0

if (right < NN) :   #  leading 1
    if ll[right] > 0 :
        ln += ll[right]
        right += 1
for i in range(0,K) :
    if (right < NN) :    #  leading 0
        if ll[right] < 0 :
            ln -= ll[right]
            right += 1
    if (right < NN) :    #  trailing 1
        if ll[right] > 0 :
            ln += ll[right]
            right += 1
    else :               #   reached to the end
        break
    
max = ln
while (right < NN) :
    if (right < NN) :    #  leading 0
        if ll[right] < 0 :
            ln -= ll[right]
            right += 1
    if (right < NN) :    #  trailing 1
        if ll[right] > 0 :
            ln += ll[right]
            right += 1
    else :                # reached to the end
        right = right  # do nothing
    
    if (left < NN) :    #  leading 1
        if ll[left] > 0 :
            ln -= ll[left]
            left += 1
    if (left < NN) :    #  trailing 0
        if ll[left] < 0 :
            ln += ll[left]
            left += 1
    if max < ln :
        max = ln

print (max)

    


Measured memory_bytes: 4980
a, b = map(int, input().split())
c = []
for i in range(a):
    d, e = map(int, input().split())
    c.append([d, e])
c.sort()
d = 0
for i in range(len(c)):
    d += c[i][1]
    if d >= b:
        print(c[i][0])
        exit()


Measured memory_bytes: 20104
#include <cstdio>
using namespace std;

int main(){
	int x, y, s;
	int a;
	int a2, b2, s2, res;
	int lb, ub, mid;
	
	while(true){
		scanf("%d%d%d", &x, &y, &s);
		if(x == 0 && y == 0 && s == 0) break;
		
		res = 0;
		for(a = 1; a < s; a++){
			ub = s; lb = 0;
			while(ub - lb > 1){
				mid = (ub + lb) / 2;
				if(mid * (100 + x) / 100 > a){
					ub = mid;
				}
				else{
					lb = mid;
				}
			}
			if(lb * (100 + x) / 100 == a){
				a2 = lb;
				ub = s; lb = 0;
				while(ub - lb > 1){
					mid = (ub + lb) / 2;
					if(mid * (100 + x) / 100 > s - a){
						ub = mid;
					}
					else{
						lb = mid;
					}
				}
				if(lb * (100 + x) / 100 == s - a){
					b2 = lb;
					s2 = (a2 * (100 + y) / 100) + (b2 * (100 + y) / 100);
					if(s2 > res){
						res = s2;
					}
				}
			}
		}
		
		printf("%d\n", res);
	}
	return 0;
}

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

void bubble_sort(int* a, int N){
    for(int i=0; i<N; i++){
        for(int j=N-1; j>i; j--){
            if(a[j] < a[j-1]){
                int tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
            }
        }
    }
}

int main(){
    int N;
    cin >> N;
    int a[N];
    for(int i=0; i<N; i++){
        cin >> a[i];
    }

    bubble_sort(a, N);

    int even_sum =0, odd_sum =0;
    for(int i=0; i<N; i++){
        if(i % 2 == 0) odd_sum += a[i];
        else even_sum += a[i];
    }
    int max_difference;
    if(N % 2 == 0) max_difference = even_sum - odd_sum;
    else max_difference = odd_sum - even_sum;
    
    cout << max_difference << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define f(i, n)         for(int i=0; i<n; i++)
#define fo(i, k, n)     for(int i=k; i<n; i++)
#define forr(i, a, b)   for(int i=a; i<=b; i++)
#define rf(i,n)         for(int i=n;i>=0;i--)
typedef unsigned long long ull;
typedef pair<int ,int> pr;
#define MAX 100005
#define INF 1000000009
#define   sq(n)         (n*n)
#define p(n) cout<<n<<endl
#define pb push_back
#define py cout<<"YES"<<endl;
#define pn cout<<"NO"<<endl;
#define __FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
ll lcm ( ll a, ll b )
{
    return ( a / __gcd ( a, b ) ) * b;
}
int main()
{
    __FastIO;

      ll n;
      cin>>n;
      if(n%1000==0)
      {
          p(0);
      }
      else
      {
          ll p=n%1000;
          p(1000-p);
      }

    return 0;
}



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

int main(){
	
	int N,A,B,C,X;
	
	while(cin>>N>>A>>B>>C>>X,N){
		int data[101];
		for(int i=1;i<=N;i++)cin>>data[i];
		int end=-1;
		for(int i=0,j=1;i<=10000;i++){
			
			if(data[j]==X){
				j++;
			}
			if(j>N){
				end=i;
				break;
			}
			X=(A*X+B)%C;
		}
		cout<<end<<endl;
	}
	
	
	
	return 0;
}


Measured memory_bytes: 1160
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		String str = scan.nextLine();
		str = scan.nextLine();
		scan.close();

		char[] c = str.toCharArray();
		int ans = 0;
		int flg = 0;
		for (int i=0; i < n; i++) {
			if (c[i] == 'A') {
				flg =1;
			} else if (flg == 1 && c[i] == 'B') {
				flg =2;
			} else if (flg == 2 && c[i] == 'C') {
				ans +=1;
				flg = 0;
			} else {
				flg = 0;
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 23124
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
 
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for (int i=0; i<n; i++){
        a[i]=i;
    }

    vector<int> p(n);
    for (int i=0; i<n; i++){
        int x;
        cin>>x;
        p[i]=x-1;
    }
    vector<int> q(n);
    for (int i=0; i<n; i++){
        int x;
        cin>>x;
        q[i]=x-1;
    }
    int count=0;
    int plen=0,qlen=0;
    do
    {
        count++;
        if(a==p)plen=count;
        if(a==q)qlen=count;
        
    } while (next_permutation(a.begin(),a.end()));
    cout<<abs(plen-qlen);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
#include <random>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <functional>
#include <random>
#include <time.h>
#include <chrono>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define MOD 1000000007
#define SORT(s) sort(s.begin(), s.end());
#define REVERSE(s) reverse(s.begin(), s.end());
#define SUM(s) accumulate(s.begin(), s.end(), 0LL);
#define P pair<int,int>
#define mp make_pair
#define valid(x,y,h,w) (0<=x&&x<h&&0<=y&&y<w)
//#define int ll
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int ndx[8] = { 0,1,0,-1, 1,1,-1,-1 };
int ndy[8] = { 1,0,-1,0, 1,-1,-1,1 };
using namespace std;
int POW(int x, int y) { return int(pow(double(x), double(y))); }
double log(double a, double b) { return log(b) / log(a); }



int main() {
	int x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;
	vector<P> z;
	rep(i, a) {
		int in;
		cin >> in;
		z.push_back(mp(in, 0));
	}
	rep(i, b) {
		int in;
		cin >> in;
		z.push_back(mp(in, 1));
	}
	rep(i, c) {
		int in;
		cin >> in;
		z.push_back(mp(in, 2));
	}

	SORT(z);
	REVERSE(z);

	ll ans = 0;
	int i = 0;
	int n = x + y;
	while (n) {
		auto v = z[i];
		int o = v.first;
		int co = v.second;
		if (co == 0) {
			if (x > 0) {
				x--;
				n--;
				ans += o;
			}
		}
		if (co == 1) {
			if (y > 0) {
				y--;
				n--;
				ans += o;
			}
		}
		if (co == 2) {
			ans += o;
			n--;
		}

		i++;
	}

	cout << ans << endl;
}




Measured memory_bytes: 6384
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int h, n ;
  int sum = 0 ;

  cin >> h >> n ;
  for (int i = 0 ; i < n ; i++ ){
    int a ;
    cin >> a ;
    sum += a ;
  }

  if (sum >= h ){
    cout << "Yes" << endl ;
  }else{
    cout << "No" << endl ;
  }

  return 0 ;
}

Measured memory_bytes: 256
n, k = map(int,input().split())
s = input()

ans = 0
change = 0

for i in range(n):
    if i ==0:
        continue
    if s[i]==s[i-1]:
        ans +=1
    else:
        change +=1


for _ in range(k):
    if change >1:
        ans +=2
        change -=2
    elif change ==1:
        ans +=1
        change -=1
    else:
        break

print(ans)
    


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,m,n) for (int i = m; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

template<typename Abel> struct UnionFind {
private:
  vector<int> par, siz;
  vector<Abel> value; //NE: neutral of abelian group
  Abel potential(int x) {
    find(x);
    return value[x];
  }

public:
  UnionFind(int n, Abel NE = 0):par(n),siz(n,1),value(n,NE) {
    for (int i = 0; i < n; ++i) par[i] = i;
  }
  int size() { return par.size();};
  int size(int x) {
    assert(x < size());
    return siz[find(x)];
  }

  int find(int x) { //return root
    assert(x < size());
    if (par[x] == x) return x;
    else {
      int r = find(par[x]);
      value[x] += value[par[x]];
      return par[x] = r;
    }
  }

  //where potential(y) - potential(x) = v
  void unite(int x, int y, Abel v) {
    assert(x < size());
    assert(y < size());
    v += potential(x); v -= potential(y);
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (siz[x] < siz[y]) std::swap(x, y), v = -v;
    siz[x] += siz[y];
    par[y] = x;
    value[y] = v;
  }

  bool same(int x, int y) { 
    assert(x < size());
    assert(y < size());
    return find(x) == find(y);
  }

  Abel diff(int x, int y) {
    assert(x < size());
    assert(y < size());
    return potential(y) - potential(x);
  }
};

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n, m;
  cin >> n >> m;
  bool ok = true;
  UnionFind<ll> uf(n);
  rep(i,m) {
    int l, r, d;
    cin >> l >> r >> d; l--; r--;
    if (!uf.same(l, r)) uf.unite(l, r, d);
    else if (uf.diff(l, r) != d) ok = false;
  }
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

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



Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
long ans=0;
void Main(){
    long long a,b,x;cin>>a>>b>>x;
    cout<<b/x-(a?a-1:-x)/x<<endl;
}
int main(){
    Main();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>
#include <bitset>
#include <sstream>
#include <cassert>
#include <time.h>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}
void printvec (vec &v) {
    Rep (i, (ll)v.size()) {
        cout << v[i] << " \n"[i+1 == (ll)v.size()];
    }
}

mat graph;
const int MOD = 1e9+7;
class mint {
    ll x;
public:
    mint(ll x = 0) : x((x % MOD + MOD) % MOD) {}
    
    mint operator -() const {
        return mint(-x);
    }
    
    mint &operator +=(const mint &a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }

    mint &operator -=(const mint &a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }

    mint &operator *=(const mint &a) {
        (x *= a.x) %= MOD;
        return *this;
    }

    mint operator +(const mint &a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint &a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator *(const mint &a) const {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(MOD - 2);
    }

    mint &operator /=(const mint &a) {
        return (*this) *= a.inv();
    }

    mint operator /(const mint &a) const {
        mint res(*this);
        return res /= a;
    }

    friend ostream &operator<<(ostream& os, const mint &m) {
        os << m.x;
        return os;
    }
};

vector<vector<mint>> dp;

void dfs (ll v, ll from) {
    // cout << v << "\n";
    mint black(1);
    mint white(1);
    for (ll nv : graph[v]) {
        if (nv == from) continue;
        dfs(nv, v);
        black *= dp[nv][1];
        white *= (dp[nv][0] + dp[nv][1]);
    }
    dp[v][0] = black;
    dp[v][1] = white;
    return;
}

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

    ll N;
    cin >> N;
    graph.assign(N, vec());
    Rep (i, N-1) {
        ll x, y;
        cin >> x >> y;
        x--; y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    dp.assign(N, vector<mint>(2, mint(0)));

    dfs(0, -1);

    // Rep (i, N) {
    //     Rep (j, 2) {
    //         cout << dp[i][j] << " \n"[j==1];
    //     }
    // }

    cout << dp[0][0] + dp[0][1] << endl;   
}

Measured memory_bytes: 21160
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

signed main() {
    int h, w, k;
    cin >> h >> w >> k;
    int x[2], y[2];
    cin >> x[0] >> y[0] >> x[1] >> y[1];
    x[0]--;
    x[1]--;
    y[0]--;
    y[1]--;
    string c[h];
    rep(i, h) {
        cin >> c[i];
    }
    const int dy[] = {0, 1, 0, -1}, dx[] = {1, 0, -1, 0};
    int dist[h][w];
    fill(dist[0], dist[h], INF);
    queue<pair<int, int>> que;
    que.emplace(x[0], y[0]);
    dist[x[0]][y[0]] = 0;
    while (!que.empty()) {
        pair<int, int> p = que.front();
        que.pop();
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= k; j++) {
                int ny = p.first + j * dy[i], nx = p.second + j * dx[i];
                if (ny < 0 || h <= ny || nx < 0 || w <= nx || c[ny][nx] == '@')
                    break;
                if (dist[ny][nx] < dist[p.first][p.second] + 1) break;
                if (dist[ny][nx] != INF) continue;
                que.emplace(ny, nx);
                dist[ny][nx] = dist[p.first][p.second] + 1;
            }
        }
    }
    cout << (dist[x[1]][y[1]] != INF ? dist[x[1]][y[1]] : -1) << endl;
    return 0;
}

Measured memory_bytes: 9636
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
using namespace std;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
#define MAX_N 1000100
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
 
ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}
 
int main(){
    ll n[3][3],x;
    bool z[3][3];
    for (ll i=0;i<3;i++)fill(z[i],z[i]+3,false);
    for (ll i=0;i<3;i++)for (ll j=0;j<3;j++)cin >> n[i][j];
    cin >> x;
    for (ll i=0;i<x;i++){
        ll a;
        cin >> a;
        for (ll j=0;j<3;j++){
            for (ll k=0;k<3;k++){
                if (n[j][k]==a){
                    z[j][k]=true;
                }
            }
        }
    }
    for (ll j=0;j<3;j++){
        for (ll k=0;k<3;k++){
            if (!z[j][k]){
                break;
            }
            if (k==2){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    for (ll j=0;j<3;j++){
        for (ll k=0;k<3;k++){
            if (!z[k][j]){
                break;
            }
            if (k==2){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    if (z[0][0] and z[1][1] and z[2][2]){
        cout << "Yes" << endl;
        return 0;
    }
    if (z[0][2] and z[1][1] and z[2][0]){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
    return 0;
}


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

#define int long long
#define double long double

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;
using P = pair<int, int>;
using ll=long long;
using ld=double;

constexpr int MOD = 1e9+7;

template<typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}

// https://twitter.com/vane11ope ←フォローしましょう
// (ノ)>◡<(ヾ)ﾓﾁﾓﾁ
signed main(signed argc, char* argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int l,r,d;
    cin>>l>>r>>d;
    cout<<r/d-(l-1)/d<<endl;
}


Measured memory_bytes: 3644
// abc162_d
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N;
    cin >> N;
    string S;
    cin >> S;

    int r = 0;
    int g = 0;
    int b = 0;
    vector<vector<int>> cnt(N, vector<int>(3, 0));
    vector<int> Color(N);
    REP(i, N) {
        if (S[i] == 'R') {r++; Color[i] = 0;}
        if (S[i] == 'G') {g++; Color[i] = 1;}
        if (S[i] == 'B') {b++; Color[i] = 2;}
        cnt[i][0] = r;
        cnt[i][1] = g;
        cnt[i][2] = b;
    }

    auto rest_color = [] (int a, int b){
        return 3 - a - b;
    };

    ll ans = 0;
    REP(i, N) {
        int a = Color[i];
        REP(j, i){
            int b = Color[j];
            // i, jが違うときだけ
            if (a == b) continue;

            // kは3-i-jでいける
            int c = rest_color(a, b);
            ans += cnt[j][c];
            int k = j - (i - j);
            if (k >= 0 && Color[k] == c) ans--;
        }
    }

    print(ans);


    return 0;
}


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

using namespace std;

int main(){
    int a,b,A,B,ans;
    ans = -1;
    cin >> a >> b;
    for (int p = 0; p <= b * 1000; p++)
    {
        A = floor((double)p * 0.08);
        B = floor((double)p * 0.1);
        if(A == a && B == b){
            ans = p;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
        

fast();
//ll t;cin>>t;while(t--)
{
    ll n,d,c=0;
    cin>>n>>d;
    for(int i=0;i<n;i++)
    {
      ll x,y;
      cin>>x>>y;
      double temp=x*x+y*y;
       double rt=sqrt(temp);
       if(rt<=d)
        c++;
    }
    cout<<c<<endl;

}
return 0;
}

Measured memory_bytes: 3668
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

ll mod = 1e9+7;

int main() {
   ll n, k; cin >> n >> k;
   vector<ll> a(n);
   bool minus = true;
   rep(i, n){
      cin >> a.at(i);
      if(a.at(i)>=0) minus = false; 
   }

   if(minus){
      ll ans = 1;
      sort(a.begin(), a.end());
      if(k%2!=0){
         sort(a.rbegin(), a.rend());
      }
      rep(i, k){
         ans *= (mod+a.at(i));
         ans %= mod;
      }
      cout << ans << endl;
      return 0;
   }

   vector<pair<ll, ll>> c;
   rep(i, n){
      int tt = 1;
      if(a.at(i)<0) tt=0;
      c.push_back(make_pair((ll)abs(a.at(i)), tt));
   }

   sort(c.rbegin(), c.rend());
   ll ans1 = 1;
   int t = 1;
   rep(i, k){
      ans1 *= (c.at(i).first);
      ans1 %= mod;
      t ^= c.at(i).second;
      t = !t;
   }

   dump(1);
   if(k==1){
      sort(a.rbegin(), a.rend());
      cout << a.at(0) << endl;
      return 0;
   }

   if(n==k){
      ll ans7 = 1;
      rep(i, n){
         ans7 *= (mod+a.at(i));
         ans7 %= mod;
      }
      cout << ans7 << endl;
      return 0;
   }

   dump(2);
   if(t==1){
      dump(3);
      cout << ans1 << endl;
      return 0;
   }
   else{
      dump(4);
      bool minus1 = true;
      rep(i, k){
         if(c.at(i).second==1){
            minus1 = false;
         }
      }
      if(minus1){
         dump(5);
         ll ans3 = 1;
         rep(i, k-1){
            ans3 *= (c.at(i).first);
            ans3 %= mod;
         }
         for(int i=k; i<n; i++){
            if(c.at(i).second){
               ans3 *= (c.at(i).first);
               ans3 %= mod;
               break;
            }
         }
         cout << ans3 << endl; 
         return 0;
      }
      else{
         ll ans4 = 1;
         ll ans5 = 1;
         int id0 = -1, id1 = -1;
         rep(i, k){
            if(c.at(i).second){
               id0 = i;
            }
            else{
               id1 = i;
            }
         }

         rep(i, k){
            if(i!=id0) ans4 *= (c.at(i).first); 
            if(i!=id1) ans5 *= (c.at(i).first);
            ans4 %= mod;
            ans5 %= mod;
         }

         int id2=-1, id3=-1;
         for(int i=k; i<n; i++){
            if(c.at(i).second==0){
               ans4 *= (c.at(i).first);
               ans4 %= mod;
               id2 = i;
               break;
            }
         }
         
         for(int i=k; i<n; i++){
            if(c.at(i).second) {
               ans5 *= (c.at(i).first);
               ans5 %= mod;
               id3 = i;
               break;
            }
         }

         if(id2==-1){
            cout << ans5 << endl;
            return 0;
         }
         
         if(id3==-1){
            cout << ans4 << endl; 
            return 0;
         }

         if(c.at(id3).first*c.at(id0).first > c.at(id1).first * c.at(id2).first){
            cout << ans5 << endl;
         }
         else{
            cout << ans4 << endl;
         }
         return 0;
      }
   }



   return 0;
}


Measured memory_bytes: 8888
// B - TAKOYAKI FESTIVAL 2019
// O(N)
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	int N; cin>>N;
	int sumD = 0, sumD2 = 0;
	rp(i, 0, N){
		int d; cin>>d;
		sumD += d;
		sumD2 += d * d;
	}
	cout<< (sumD*sumD - sumD2)/2 <<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

struct queues {
	char name[11];
	int time;
	int pre;
	int next;
};

int main( void ) 
{
	struct queues ps[100001];
	int i;
	int n,q;
	int cnt,cur;
	int time,res;
	int head;
	
	scanf( "%d%d", &n, &q );
	head=0;
	for( i=0; i<n; i++ ) {
		scanf( "%s%d", ps[i].name, &ps[i].time );
		ps[i].pre=i-1;
		ps[i].next=i+1;
	}
	
	res=time=cnt=0;
	cur=head;
	while( cnt<n ) {
		res=ps[cur].time-q;
		if( res <= 0 ) {
			time+=ps[cur].time;
			ps[cur].time=time;
			printf( "%s %d\n", ps[cur].name, ps[cur].time );
			
			if( -1 == ps[cur].pre ) {
				head=ps[cur].next;
				ps[head].pre=-1;
			} else {
				ps[ ps[cur].pre ].next=ps[cur].next;
				ps[ ps[cur].next ].pre=ps[cur].pre;
			}
			cnt++;
		} else {
			time+=q;
			ps[cur].time=res;
		}
		cur=ps[cur].next;
		
		if( n<=cur ) { 
			cur=head;
		}	
	}
	
	return 0;
}

Measured memory_bytes: 1780