akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <functional>

using namespace std;
static const long long int INF = 1e16;
typedef pair<int, int> P;


void solve()
{
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	int width = tx - sx;
	int height = ty - sy;
	for (int i = 0; i < height; ++i)
	{
		cout << 'U';
	}
	for (int i = 0; i < width; ++i)
	{
		cout << 'R';
	}

	for (int i = 0; i < height; ++i)
	{
		cout << 'D';
	}
	for (int i = 0; i < width; ++i)
	{
		cout << 'L';
	}

	cout << 'L';
	for (int i = 0; i < height + 1; ++i)
	{
		cout << 'U';
	}
	for (int i = 0; i < width + 1; ++i)
	{
		cout << 'R';
	}
	cout << 'D';

	cout << 'R';
	for (int i = 0; i < height + 1; ++i)
	{
		cout << 'D';
	}
	for (int i = 0; i < width + 1; ++i)
	{
		cout << 'L';
	}
	cout << 'U' << endl;
}

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

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

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

    int n, t;
    cin >> n >> t;

    int prev;
    cin >> prev;
    int res = 0;
    int begin = prev;
    int end = prev + t;

    rep1(i, n){
        int next;
        cin >> next;

        if(next-prev <= t) end = next + t;
        else {
            res += end - begin;
            begin = next;
            end = next + t;
        }
        prev = next;
    }
    res += end - begin;
    cout << res << endl;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	private static FastScanner sc = new FastScanner();

	public static void main(String[] args) {
		int n = sc.nextInt();
		Point[] p = new Point[n];
		for(int i=0; i<n; i++) {
			p[i] = new Point(sc.nextDouble(), sc.nextDouble());
		}
		
		double maxdist = distance(p[0], p[1]);
		int j = 1;
		for(int i=2; i<n; i++) {
			double dist = distance(p[0], p[i]);
			if(dist > maxdist) {
				maxdist = dist;
				j = i;
			}
		}
		
//		System.out.println(0 + " " + j + " " + maxdist);
		
		for(int i=1; i<n; i++) {
			double maxdist2 = distance(p[i], p[j%n]);
			while(true) {
				double dist = distance(p[i], p[(j+1)%n]);
				if(dist > maxdist2) {
					maxdist2 = dist;
					j++;
				} else {
					break;
				}
			}
			
//			System.out.println(i + " " + j + " " + maxdist2);
			
			if(maxdist2 > maxdist) {
				maxdist = maxdist2;
			}
		}
		
		System.out.println(maxdist);
		
	}
	
	static double distance(Point p1, Point p2) {
		return Math.sqrt((p2.x-p1.x)*(p2.x-p1.x) + (p2.y-p1.y)*(p2.y-p1.y));
	}

	static class Point {
		double x;
		double y;
		Point(double x, double y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}

Measured memory_bytes: 63776
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <sstream>
#include <algorithm>
#include <queue>
#include <stack>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <cctype>
#include <climits>

using namespace std;

using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vb = vector<bool>;

using ll = long long int;

#define mp(a,b) make_pair(a,b)

const int MOD = 1000 * 1000 * 1000 + 7;

struct tVer {
	int per;
	bool ver;
};

bool comprobar(vector<vector<tVer>> const& testimonios, vb const& res) {
	for (int i = 0; i < testimonios.size(); ++i) {
		if (res[i]) {
			for (int j = 0; j < testimonios[i].size(); ++j) {
				if (testimonios[i][j].ver != res[testimonios[i][j].per]) return false;
			}
		}
	}
	return true;
}

//True honest
void backtrack(int pact, int ptot, vb & res, int & maxi, int nh, vector<vector<tVer>> const& testimonios) {
	if (pact == ptot) {
		//comprobar
		if (comprobar(testimonios, res)) {
			maxi = max(maxi, nh);
		}
	}
	else {
		res.push_back(true);
		backtrack(pact + 1, ptot, res, maxi, nh + 1, testimonios);
		res.pop_back();
		res.push_back(false);
		backtrack(pact + 1, ptot, res, maxi, nh, testimonios);
		res.pop_back();
	}
}

bool res() {
	int n;
	cin >> n;
	if (!cin) return false;

	vb honestos;
	vector<vector<tVer>> mat(n);
	for (int i = 0; i < n; ++i) {
		int ai;
		cin >> ai;

		for (int j = 0; j < ai; ++j) {
			int x, y;
			cin >> x >> y;
			tVer aux;
			aux.per = x - 1;
			if (y == 0) aux.ver = false;
			else aux.ver = true;
			mat[i].push_back(aux);
		}
	}


	int m = 0;

	backtrack(0, n, honestos, m, 0, mat);

	cout << m << '\n';

	return true;
}

int main() {
	while (res()) {}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>
#include <stack>
#include <tuple>
#include <array>
using namespace std;
#define rep(i,n) for (int i=0; i < (n); i++)


typedef long long int ll;
typedef double D;      // ??§?¨?????????????double???long double?????????
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
typedef vector<P> VP;


const int INF = (1<<30) - 1;
const D EPS = 1e-9;

#define X real()
#define Y imag()
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)

//x, y, t
typedef tuple<int, int, int> State;

const int DIFF = 150;
//x, y
bool can_move[300][300];
//x, y, t%6
int d[300][300][6];

//g++ -std=c++0x -msse4.2 -O3
//#include <bits/stdc++.h>
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.precision(16);
    
    for(int i=0; i<300; i++)
        for(int j=0; j<300; j++)
            can_move[i][j] = true;
    
    for(int i=0; i<300; i++)
        for(int j=0; j<300; j++)
            for(int k=0; k<6; k++)
                d[i][j][k] = INF;
    
    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    int n; cin >> n;
    while(n--){
        int x, y; cin >> x >> y;
        can_move[DIFF+x][DIFF+y] = false;
    }
    int lx, ly; cin >> lx >> ly;
    
    priority_queue<pair<int, State>, vector<pair<int, State>>, greater<pair<int, State>>> que;
    d[DIFF+sx][DIFF+sy][0] = 0;
    que.push(make_pair(d[DIFF+sx][DIFF+sy][0], State(DIFF+sx, DIFF+sy, 0)));
    
    while(!que.empty()){
        auto p = que.top(); que.pop();
        int x, y, t;
        tie(x, y, t) = p.second;
        if(p.first > d[x][y][t%6]) continue;
        
        int dx[] = {0, 1, 1, 0, -1, -1, 0};
        int dy[] = {1, x%2, x%2-1, -1, x%2-1, x%2, 0};
        for(int i=0; i<7; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(abs(nx-DIFF)>lx || abs(ny-DIFF)>ly || !can_move[nx][ny]) continue;
            
            if(d[x][y][t%6] + ((abs(x-DIFF)*abs(y-DIFF)*t)%6 != i) < d[nx][ny][(t+1)%6]){
                d[nx][ny][(t+1)%6] = d[x][y][t%6] + ((abs(x-DIFF)*abs(y-DIFF)*t)%6 != i);
                //cout << nx-DIFF << " " << ny-DIFF << " " << t+1 << " " << d[nx][ny][(t+1)%6] << endl;
                que.push(make_pair(d[nx][ny][(t+1)%6], State(nx, ny, t+1)));
            }
        }
    }
    
    int ans = INF;
    for(int i=0; i<6; i++)
        ans = min(ans, d[DIFF+gx][DIFF+gy][i]);
    
    cout << (ans == INF ? -1: ans) << endl;
    return 0;
}

Measured memory_bytes: 3532
#■標準入力ショートカット


def get_next_int():
    return int(float(input()))


def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])


def get_next_str():
    return input()


def get_next_strs(delim=" "):
    return tuple(input().split(delim))


def get_next_by_types(*value_types, delim=" "):
    return tuple([t(x) for t, x in zip(value_types, input().split(delim))])


def solve():
    N = get_next_int()
    upper_line = get_next_ints()
    lower_line = get_next_ints()

    up_dp = [0]*N
    low_dp = [0]*N

    up_dp[0] = upper_line[0]
    low_dp[N-1] = lower_line[N-1]
    for i in range(1, N):
        up_dp[i] = up_dp[i-1] + upper_line[i]
        low_dp[N-i-1] = low_dp[N-i] + lower_line[N-i-1]
    max_candies = 0
    for i in range(N):
        max_candies = max(max_candies, up_dp[i] + low_dp[i])
    print(max_candies)

solve()

Measured memory_bytes: 3064
import math
def main():
  X, K, D = map(int, input().split())
  if abs(X) >= K * D:
    print(abs(X)-K*D)
  else:
    Y = math.ceil(abs(X) / D)
    if (K-Y) % 2 == 0:
      print(D*Y-abs(X))
    else:
      Z = abs(X)-D*(Y-1)
      print(Z)
main()

Measured memory_bytes: 62144
package main

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

func solve() {
	x := getInt()

	ans := 0
	a := x / 100
	b := x % 100
	if b <= 5*a {
		ans = 1
	}
	fmt.Fprintln(wr, ans)
}

// -----------------------------------------

const (
	inf = 1 << 60
	// mod = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}

func getRunes() []rune {
	return []rune(getString())
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;

int main() {
	int N, M, C;
	cin >> N >> M >> C;

	//長さMの配列を作る。要素を0で初期化する
	vector<int> B(M, 0);
	for (int i = 0; i < M; i++)
	{
		cin >> B[i];
	}


	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		vector<int> Ai(M);
		for (int j = 0; j < M; j++)
		{
			cin >> Ai[j];
		}

		int sum = 0;
		for (int j = 0; j < M; j++)
		{
			sum += Ai[j] * B[j];
		}
		sum += C;
		if (sum > 0) ans++;
	}

	cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<stdlib.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
int main(void){
    string S;
    ll N,K;
    cin >> N >> K;
    cin >> S;
    ll T[100000]={},F[100000]={};
    ll num[2]={};

    if(S[0]%2 == 0){
        num[1] = 1;
        F[0] = 0;
    }
    rep(i,N){
        if(S[i]%2 == 0)T[num[0]]++;
        else F[num[1]]++;
        if(i<N-1){
            if(S[i]%2==0 && S[i+1]%2==1)num[0]++;
            if(S[i]%2==1 && S[i+1]%2==0)num[1]++;
        }
    }
    if(S[N-1]%2==0){
        F[num[1]] =0;
        num[0]++;
    }
    //cout << num[0] << " " << num[1] <<endl;
    //rep(i,num[0]) cout <<F[i] << " " << T[i] << " " ;
    //cout << F[num[0]] << endl;
    
    ll sum=0;
    rep(i,min(num[0],K))sum+=(T[i]+F[i]);
    sum +=F[min(num[0],K)];
    //cout << sum << endl;
    ll ans=sum;
    for(ll i=0;i+K<num[0];i++){
        sum = sum - F[i] - T[i] + T[i+K] + F[i+K+1];
        ans = max(ans,sum);
    }
    cout << ans << endl;
}


Measured memory_bytes: 2048
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}
ll S(ll n){
    ll s = 0;
    while(n!=0){
        s += n%10;
        n /= 10;
    }
    return s;
}
int main(){
    int k;
    cin >> k;
    int c = 0;
    ll base = 1;
    ll ss = 0;
    vector<ll> res;
    for(int i=0;i<15;i++){
        for(ll i=1;i<=1000;i++){
            ll K = i*base+ss;
            ll P = (i+1)*base+ss;
            if(K*S(P)<=P*S(K)){
                res.push_back(K);
            }else{
                break;
            }
        }
        base*=10;
        ss *=10;
        ss += 9;
    }
    sort(all(res));
    res.erase(unique(all(res)),res.end());
    rep(i,k){
        cout << res[i] << endl;
    }
    return 0;
}


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

#define INF (INT64_MAX)
#define MOD (1000000000+7)
#define MAX 100000

long long H, W;
int N;
long long a[MAX];
long long b[MAX];

typedef pair<long long, long long> P;
typedef pair<P, long long> PP;
map<P, long long> m;
vector<PP> v;

long long c[10];

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

	for( int i = 0; i < N; i++ ) {
		for( int j = 0; j < 3; j++ ) {
			for( int k = 0; k < 3; k++ ) {
				int nx = b[i] - k - 1;
				int ny = a[i] - j - 1;
				if( nx < 0 || W - 3 < nx || ny < 0 || H - 3 < ny ) {
					continue;
				}
				P p = P( nx, ny );
				m[p]++;
			}
		}
	}
	for( auto it = m.begin(); it != m.end(); it++ ) {
		v.push_back( *it );
	}
	sort( v.begin(), v.end(), []( PP aa, PP bb ) { return aa.second < bb.second; } );
	long long sum = 0;
	auto it = v.begin();
	for( int i = 1; i < 10; i++ ) {
		while( it < v.end() && it->second == i ) {
			c[i]++;
			sum++;
			it++;
		}
	}
	while( it < v.end() ) {
		sum++;
		it++;
	}
	c[0] = (H - 2) * (W - 2) - sum;

	for( int i = 0; i < 10; i++ ) {
		cout << c[i] << endl;
	}

	return 0;
}


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

int main()
{
    string S;
    int K;
    cin>>S>>K;

    vector<int> A(1);
    for (char x: S)
        if (x=='0')
            A.push_back(0);
        else
            A.back()++;

    int n = (int)A.size();
    int n1 = 0;
    for (char x: S)
        if (x=='1')
            n1++;
    K = min(K, n1);

    long long M = 998244353;
    vector<vector<long long>> T(K+1, vector<long long>(n1+1));
    T[0][0] = 1;
    for (int i=n-1; i>=0; i--)
    {
        vector<vector<long long>> P(K+1, vector<long long>(n1+1));
        P.swap(T);
        for (int j=0; j<=K; j++)
            for (int k=0; k<=K; k++)
                if (P[j][k]>0)
                    for (int l=0; l<=n1; l++)
                    {
                        int j2 = j+max(A[i]-l, 0);
                        int k2 = k+A[i]-l;
                        if (j2<=K && 0<=k2)
                        {
                            T[j2][k2] += P[j][k];
                            T[j2][k2] %= M;
                        }
                    }
    }
    long long ans = 0;
    for (int i=0; i<=K; i++)
        ans += T[i][0];
    cout<<ans%M<<endl;
}


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

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

  ll MOD = 1e9 + 7;
  int N; cin >> N;
  vector<int> C(N, 0);
  for (int i = 0; i < N; i++) {
    int c; cin >> c; c--;
    C[i] = c;
  }

  vector<ll> ans(N, 0);
  vector<ll> pos(2e5 + 10, -1);

  for (int i = 0; i < N; i++) {
    int c = C[i];
    if (pos[c] != -1 && C[i] != C[i - 1]) {
      int p = pos[c];
      ans[i] = (ans[i - 1] + ans[p] + 1) % MOD;
    } else if (i > 0) {
      ans[i] = ans[i - 1];
    }
    pos[c] = i;
  }
  cout << (ans[N - 1] + 1) % MOD << '\n';

  return 0;
}

Measured memory_bytes: 4224
import java.util.Scanner;


public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] a = new int[N];

        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
        }

        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if ((i + 1) % 2 != 0 && a[i] % 2 != 0) {
                cnt++;
            }
        }

        System.out.println(cnt);

    }

}


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

    if(s[0] == 'S')cout << "Cloudy" << endl;
    else if(s[0] == 'C')cout << "Rainy" << endl;
    else cout << "Sunny" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cassert>
#include<vector>
#define ll long long
using namespace std;
inline int read(){
	int re=0,flag=1;char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-') flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
	return re*flag;
}
int n,m,l[300010],r[300010],ans[100010],a[100010];
vector<int>q[100010];
int lowbit(int x){
	return x&(-x);
}
void change(int x,int val){
//	cout<<"change "<<x<<' '<<val<<'\n';
	for(;x<=m;x+=lowbit(x)) a[x]+=val;
}
int sum(int x){
	int re=0;
//	cout<<"getsum "<<x<<' ';
	for(;x>0;x-=lowbit(x)) re+=a[x];
//	cout<<re<<'\n';
	return re;
}
int main(){
	n=read();m=read();int i,j,ans,totn=n;
	for(i=1;i<=n;i++){
		l[i]=read();r[i]=read();
		q[r[i]-l[i]+1].push_back(l[i]);
	}
	for(j=1;j<=m;j++){
		for(i=0;i<q[j].size();i++){
			change(q[j][i],1);change(q[j][i]+j,-1);
		}
		ans=0;totn-=q[j].size();
		for(i=j;i<=m;i+=j) ans+=sum(i);
		printf("%d\n",ans+totn);
	}
}

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

const int N = 19;

int n, m;
long long ans = 0;
bool b[N]={};
vector<int> adj[N];

void dfs(int u, int cnt){
    if(cnt == n){
        ans++;
        return;
    }

    b[u] = true;
    for(int v : adj[u]){
        if(!b[v]){
            dfs(v, cnt+1);
        }
    }
    b[u] = false;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++){
        int x, y; scanf("%d%d",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs(1,1);

    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 384
import sys
sys.setrecursionlimit(10**6)

n = int(input())
MOD = 10**9+7

dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(101)]

# ATCGは0123と読み替える
# 長さ0の文字列は1。0,1,2に関する制約しかないので、Sは333Sと考えても問題がない
dp[0][3][3][3] = 1

# 文字列の文字数
for length in range(n):
    # 最後から1文字目の文字
    for c1 in range(4):
        # 最後から2文字目の文字
        for c2 in range(4):
            # 最後から3文字目の文字
            for c3 in range(4):
                # 条件に当てはまる物がない場合はcontinue
                if dp[length][c1][c2][c3] == 0: continue
                # 新しく追加する文字
                for a in range(4):
                    
                    # ダメな5条件をカット
                    if a==2 and c1==1 and c2==0: continue
                    if a==2 and c1==0 and c2==1: continue
                    if a==1 and c1==2 and c2==0: continue
                    if a==2 and c1==1 and c3==0: continue
                    if a==2 and c2==1 and c3==0: continue
                    
                    # ダメな条件を抜けたら、aを足した文字列を作れる
                    # S = ... c3 c2 c1
                    # nextS = ... c2 c1 a
                    dp[length+1][a][c1][c2] += dp[length][c1][c2][c3]
                    dp[length+1][a][c1][c2] %= MOD
                    
ans = 0
# 最後から1文字目の文字
for c1 in range(4):
    # 最後から2文字目の文字
    for c2 in range(4):
        # 最後から3文字目の文字
        for c3 in range(4):
            # 長さnの文字列の値をまとめる
            ans += dp[n][c1][c2][c3]
            ans %= MOD
            
print(ans)

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

using namespace std;

const int N = 1e5 + 5;

int n, a[N], cnt[N], cnt2[N];

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i += 2) cnt[a[i]]++;
    for (int i = 2; i <= n; i += 2) cnt2[a[i]]++;

    int Max = 0, Max2 = 0, pos = 0, pos2 = 0;
    for (int i = 1; i <= 100000; i++) {
        if (cnt[i] > Max) {
            Max2 = Max;
            pos2 = pos;
            Max = cnt[i];
            pos = i;
        }
        else if (cnt[i] > Max2) {
            Max2 = cnt[i];
            pos2 = i;
        }
    }

    vector <pair <int, int> > v1, v2;
    v1.push_back({Max, pos}); v1.push_back({Max2, pos2});
    Max = 0, Max2 = 0, pos = 0, pos2 = 0;

    for (int i = 1; i <= 100000; i++) {
        if (cnt2[i] > Max) {
            Max2 = Max;
            pos2 = pos;
            Max = cnt2[i];
            pos = i;
        }
        else if (cnt2[i] > Max2) {
            Max2 = cnt2[i];
            pos2 = i;
        }
    }

    v2.push_back({Max, pos}); v2.push_back({Max2, pos2});
    if (v1[0].second != v2[0].second) printf("%d", n - v1[0].first - v2[0].first);
    else {
        int ans = max(v1[0].first + v2[1].first, v1[1].first + v2[0].first);
        printf("%d", n - ans);
    }
    return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

const ll M = 1000000007;

ll modpow(ll x,int k){
	ll ret = 1 , t = x;
	while(k > 0){
		if(k&1){ ret *= t; ret %= M; }
		t *= t; t %= M;
		k >>= 1;
	}
	return ret;
	/*if(k == 0)return 1;
	ll ret = modpow(x,k/2);
	ret *= ret; ret %= M;
	if(k%2 == 1){ ret *= x; ret %= M ; }
	return ret;*/
}
ll inv(ll x){
	return modpow(x,(int)M-2);
}

ll f[4000010];
void init(int k){
	f[k-2] = 1;
	for(int i = k-2 ; i < 4000009 ; i ++){
		f[i+1] = f[i]*(i+1); f[i+1] %= M;
		f[i+1] *= inv(i+3-k); f[i+1] %= M;
	}
}

int main(){
	ll n,k;
	cin >> n >> k;
	if(k == 1){
		puts("1");
		return 0;
	}
	if(k == 2){
		rep(i,4000010)f[i] = 1;
	}
	if(k != 2)init(k);
	
	static ll dp[2002][2002] = {};
	dp[0][0] = 1;
	rep1(i,n){
		ll sum = dp[i-1][i-1];
		for(int j = i ; j <= n ; j ++){
			sum += dp[i-1][j];
			if(sum >= M)sum -= M;
			dp[i][j] = sum*f[(n-i)*k+i-j+k-2];
			dp[i][j] %= M;
		}
	}
	rep1(i,n){
		dp[n][n] *= i;
		dp[n][n] %= M;
	}
	cout << dp[n][n] << endl;
}
				



Measured memory_bytes: 54144
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> vec(3, 0);
    for(int n=0; n<N; n++) {
        long long int a;
         cin >> a;
         if(a%4) {
            if(a%2) {
                vec[a%2]++;
            } else {
                vec[a%4]++;
            }
         } else {
            vec[a%4]++;
         }
    }
    
    if(vec[1]-vec[0]>1) {
        cout << "No" << endl;
    } else {
        if(vec[1]-vec[0]==1) {
            if(vec[2]) {
                cout << "No" << endl;
            } else {
                cout << "Yes" << endl;
            }
        } else {
            cout << "Yes" << endl;
        }
    }
    

    return 0;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
int h[100005];
int a[100005];
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&h[i]);
	}
	int ans=0;
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(h[i]<=h[i-1]) cnt++;
		else cnt=0;
		ans=max(ans,cnt);
	}
	printf("%d\n",ans);
	return 0;
}


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

template <typename T>
class DualSegmentTree {
 public:
  using Operation = std::function<T(T, T)>;
  DualSegmentTree(int size, Operation operation, T identity = T())
      : operation_(operation), identity_(identity) {
    int two = 1;
    while (two < size) {
      two <<= 1;
    }
    v_.resize(two * 2 - 1, identity_);
  }
  void Update(int begin, int end, T v) {
    std::function<void(int, int, int)> rec = [&](int cbegin, int cend,
                                                 int index) {
      if (begin <= cbegin && cend <= end) {
        v_[index] = operation_(v_[index], v);
        return;
      }
      if (cend <= begin || end <= cbegin) {
        return;
      }
      int cmid = (cbegin + cend) / 2;
      rec(cbegin, cmid, index * 2 + 1);
      rec(cmid, cend, index * 2 + 2);
    };
    rec(0, (v_.size() + 1) / 2, 0);
  }
  T Get(int i) const {
    T v = identity_;
    int index = v_.size() / 2 + i;
    while (true) {
      v = operation_(v, v_[index]);
      if (index == 0) break;
      index = (index - 1) / 2;
    }
    return v;
  }

 private:
  const Operation operation_;
  const T identity_;
  std::vector<T> v_;
};

#if DEBUG
template <typename T>
void debug(const T& value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(const T& value, const Ts&... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                        \
  do {                                  \
    cerr << #__VA_ARGS__ << ": ";       \
    debug(__VA_ARGS__);                 \
    cerr << " (L" << __LINE__ << ")\n"; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define rd(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << '\n';
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define wt(...) write_to_cout(__VA_ARGS__);

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

using ll = long long;

template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;

using namespace std;

struct Monster {
  ll X, H;
  bool operator<(const Monster& m) const { return X < m.X; }
};

Monster monster[200000];

ll Add(ll a, ll b) { return a + b; }

int main() {
  rd(ll, N, D, A);
  rep(i, N) cin >> monster[i].X >> monster[i].H;
  sort(monster, monster + N);

  DualSegmentTree<ll> tree(N, Add);
  rep(i, N) tree.Update(i, i + 1, monster[i].H);

  ll ans = 0;
  int mi = 0;
  while (mi < N) {
    int h = tree.Get(mi);
    if (h <= 0) {
      ++mi;
      continue;
    }
    Monster max_m = {monster[mi].X + D * 2, 0};
    int ub = upper_bound(monster, monster + N, max_m) - monster;
    ll cnt = (h + A - 1) / A;
    tree.Update(mi, ub, -cnt * A);
    ans += cnt;
  }
  wt(ans);
}


Measured memory_bytes: 10372
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <bits/stdc++.h>
#include<queue>
#include <numeric>
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define fore(i,a) for(auto &i:a)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
 



int main(){
    string S;
    cin >> S;
    bool exist_A=false;
    bool exist_B=false;
    for(int i=0;i<S.length();++i){
        if('A'==S[i]){
            exist_A=true;
        }
        else{
            exist_B=true;
        }
    }
    if(exist_A){
        if(exist_B){
            cout << "Yes";
        }
        else{
            cout << "No";
        }
    }
    else{
        cout << "No";
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4+100;
int n,ans,nex[N][10],pos[10];
char s[N];
void dfs(int d,int cur){
    if(d==3){
        ans++; return;
    }
    for(int i=0;i<10;++i){
        if(nex[cur][i]==-1) continue;
        dfs(d+1,nex[cur][i]);
    }
}
int main(){
    scanf("%d%s",&n,s+1);
    for(int i=0;i<10;++i) pos[i]=-1;
    for(int i=n;i>=0;--i){
        for(int j=0;j<10;++j)
            nex[i][j]=pos[j];
        if(i) pos[s[i]-'0']=i;
    }
    ans=0; dfs(0,0);
    printf("%d\n",ans);
}

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

using namespace std;

const int MOD = 1e9 + 7;

long long mypow(long long x, long long y) {
	long long tot = 1LL;
	while (y) {
		if (y & 1) tot = (tot * x) % MOD;
		y >>= 1;
		x = x * x % MOD;
	}
	return tot;
}

long long ans[100005];

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	
	for (int i = k; i >= 1; i--) {
		int x = k / i;
		long long cur = mypow(x, n);
		for (int j = 2; j <= k / i; j++) {
			cur = (cur - ans[j * i] + MOD) % MOD;
		}
		ans[i] = cur;
	}
	
	long long res = 0;
	
	for (int i = 1; i <= k; i++) res = (res + 1LL * i * ans[i]) % MOD;
	
	printf("%lld\n", res);
}


Measured memory_bytes: 4488
f _ _ [] = []
f a b ('a':s) | a+b>0 = "Yes" : f (a-1) b s
f a b ('b':s) | a+b>0 && b>0 = "Yes" : f a (b-1) s
f a b (_:s) = "No" : f a b s
main = do
  [_,a,b] <- fmap (map read . words) getLine
  s <- getLine
  mapM_ putStrLn $ f a b s

Measured memory_bytes: 5372
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <iostream>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

typedef long long ll;
const int MOD = 998244353;

ll mypow(ll x, ll n) {
  if(n == 0) return 1;
  if(n % 2 == 0) return mypow(x*x%MOD, n/2);
  return mypow(x*x%MOD, n/2)*x%MOD;
}

int cmb[4010][4010];
inline ll h(int a, int b) {
  if(b < 0) return 0;
  return cmb[a+b-1][b];
}

int main(void) {
  REP(i, 4010) {
    cmb[i][0] = 1;
    REP(j, i) {
      cmb[i][j+1] = (cmb[i-1][j] + cmb[i-1][j+1]) % MOD;
    }
  }
  int k, n;
  scanf("%d%d", &k, &n);
  for(int i = 2; i <= 2*k; ++i) {
    ll cur = 0;
    int half = min(i, 2*k+2-i) / 2;
    for(int j = 1; j <= half; ++j) {
      if(j % 2 == 1) {
        cur += h(k,n-j*2) * cmb[half][j] % MOD;
        cur %= MOD;
      } else {
        cur += MOD - h(k,n-j*2) * cmb[half][j] % MOD;
        cur %= MOD;
      }
    }
    printf("%lld\n", (h(k, n) - cur + MOD) % MOD);
  }
  
  return 0;
}


Measured memory_bytes: 61568
import sys
n, m = map(int, sys.stdin.readline().split(' '))
a = [0] * (2 * m)
for i in range(m):
    a[2 * i], a[2 * i + 1] = map(int, sys.stdin.readline().split(' '))
a.sort()
flag = False
tmp = 0
crr = 0
for i in range(2 * m):
    nxt = a[i]
    if crr == nxt:
        tmp += 1
    else:
        if tmp & 1:
            flag = True
            break
        tmp = 1
    crr = nxt
if not flag:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 11808
/** 
 *  Author : Parth Prajapati aka (PARTH_4399, hungry_chef)
 *  Institute : Pandit Deendayal Petroleum University
 **/
#include<bits/stdc++.h>

using namespace std; 

#define start_cooking int main()
#define food_is_ready return 0;
#define main_ingredient_added ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

void cook()
{
    // start with your recipe
    string s;
    cin>>s;
    for(auto i : s)
    {
        if(i == '?')    cout<<"D";
        else    cout<<i;
    }
}

start_cooking
{
    main_ingredient_added
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t = 1;
    //cin>>t;
    while(t--)
        cook();
    food_is_ready
}

Measured memory_bytes: 3776
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,m,s,t;
vector<P>edge[1000005];
ll dist[1000005];
ll dist2[1000005];
ll way[1000005];
ll way2[1000005];

int main(){
	cin>>n>>m;
	cin>>s>>t;
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		edge[a].pb(mp(b,c));
		edge[b].pb(mp(a,c));
	}
	priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >que;
	fill(dist,dist+n+5,1e18);
	dist[s] = 0; way[s] = 1;
	que.push(mp(0,s));
	while(!que.empty()){
		pair<ll,int>p = que.top(); que.pop();
		if(dist[p.sc] != p.fi) continue;
		for(int i=0;i<edge[p.sc].size();i++){
			int to = edge[p.sc][i].fi;
			ll cs = edge[p.sc][i].sc;
			if(dist[to] > dist[p.sc]+cs){
				dist[to] = dist[p.sc]+cs;
				way[to]  = way[p.sc];
				que.push(mp(dist[to],to));
			}
			else if(dist[to] == dist[p.sc]+cs){
				way[to] += way[p.sc];
				way[to] %= mod;
			}
		}
	}
	fill(dist2,dist2+n+5,1e18);
	dist2[t] = 0; way2[t] = 1;
	que.push(mp(0,t));
	while(!que.empty()){
		pair<ll,int>p = que.top(); que.pop();
		if(dist2[p.sc] != p.fi) continue;
		for(int i=0;i<edge[p.sc].size();i++){
			int to = edge[p.sc][i].fi;
			ll cs = edge[p.sc][i].sc;
			if(dist2[to] > dist2[p.sc]+cs){
				dist2[to] = dist2[p.sc]+cs;
				way2[to] = way2[p.sc];
				que.push(mp(dist2[to],to));
			}
			else if(dist2[to] == dist2[p.sc]+cs){
				way2[to] = (way2[to]+way2[p.sc])%mod;
			}
		}
	}
	ll ans = 0;
	for(int i=1;i<=n;i++){
	    if(dist[i] == dist2[i] && dist[i] + dist2[i] == dist[t]){
	        ans += way[i] % mod * way[i] % mod * way2[i] % mod * way2[i] % mod;
	        ans %= mod;
	    }
		for(int j=0;j<edge[i].size();j++){
			if(dist[i]+edge[i][j].sc+dist2[edge[i][j].fi] == dist[t]){
				ll L1 = dist[i],R1 = dist[edge[i][j].fi];
				ll L2 = dist2[edge[i][j].fi],R2 = dist2[i];
				if(L1 < R2 && L2 < R1){
					ans += way[i] % mod * way[i] % mod * way2[edge[i][j].fi] % mod * way2[edge[i][j].fi] % mod;
					ans %= mod; 
				}
			}
		}
	}
	assert(way2[s] == way[t]);
	assert(dist[t] == dist2[s]);
	way[t] %= mod;
	ans = way[t] * way[t] % mod - ans;
	ans = (ans%mod+mod)%mod;
	cout << ans << endl;
}

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

using namespace std;

int main()
{	
	int n;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i < n; i++)
	{
		cin >> h.at(i);
	}

	int max = 0;
	bool flag = true;
	for (int i = 1; i < n; i++)
	{
		if (max < h.at(i - 1))
		{
			max = h.at(i - 1);
		}
		if (1 < max - h.at(i))
		{
			flag = false;
			break;
		}
	}

	cout << (flag ? "Yes" : "No") << endl;
}

Measured memory_bytes: 640
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(S: str):
    s = [0] * 2019
    s[0] = 1
    ret = 0
    for c in S:
        cc = int(c)
        n = [0] * 2019
        for k, v in enumerate(s):
            kk = (k * 10 + cc) % 2019
            n[kk] += v
            if kk == 0:
                ret += v
        s = n
        n[0] += 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 76528
#include <stdio.h>
#include <iostream>
using namespace std;

long long A[100009];
long long B[100009];

int main()
{
	int ret;

	int N;

	ret = scanf("%d", &N);

	int l, i = 1;
	while (cin >> l) {
		if (i <= N + 1) {
			A[i] = l;
		}
		else {
			B[i - N - 1] = l;
		}
		i++;
	}

	long long count = 0;
	for (int i = 1; i <= N; i++) {
		long long c;
		if (A[i] < B[i]) { c = A[i]; }
		else             { c = B[i]; }
		A[i] -= c;
		B[i] -= c;
		count += c;

		if (A[i + 1] < B[i]) { c = A[i + 1]; }
		else                 { c = B[i]; }
		A[i + 1] -= c;
		B[i]     -= c;
		count += c;
	}

	printf("%lld", count);

end:
	return 0;
}



Measured memory_bytes: 1792
#include <stdio.h>

void print(long x,long y){
  long z;
  if(x-y>=0){
    z = x-y;
  }else{
    z = -1;
  }
  printf("%ld",z);
  return ;
}

int main(void){
  long num,m;
  scanf("%ld",&num);
  scanf("%ld",&m);
  long a[m];
  long sum=0;
  for(int i=0;i<m;i++){
    scanf("%ld",&a[i]);
    sum+=a[i];
    }
  print(num,sum);
  return 0;
}


Measured memory_bytes: 1748
/*
 * Author: .-O_O-.
 */
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define rep0(a,b) for(int a=0;a<b;a++)
#define rep1(a,b) for(int a=1;a<=b;a++)
#define repp(a,b,c) for(int a=b;a<c;a++)
#define in insert
#define len length()
#define si size()
#define lb lower_bound
#define ub upper_bound
#define beg begin()
#define en end()
#define f first
#define s second
#define pr(a) cout<<a
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define nx cout<<"\n"
#define int long long
const ll mod = 1000000007;
const ll maxn = 200050;
const ll mm = 1e+18;
int f[maxn];
int a[maxn];
void solve()
{
    int n;
    cin>>n;
    rep1(i,n) cin>>a[i];
    rep1(i,n){
        if(i+1-a[i]>=1) f[i+1-a[i]]++;
    }
    int ans=0;
    rep1(i,n){
        if(i+a[i]+1<=n) ans+=f[i+a[i]+1];
    }
    pr(ans);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //srand(time(0));
    //freopen("sp.txt","w",stdout);
    //cin>>t;
    rep1(_i,t){
        //cout<<"Case #"<<_i<<": ";
        solve();
        //nx;
    }
    return 0;
}


Measured memory_bytes: 6764
#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
// #include <map>
// #include <algorithm>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

template<typename T>
T mod(T a, T b){
    return (a + b) % b;
}

template<typename T>
T gcd(T a, T b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

// n を素因数分解
map<ll, ll> factor(ll n){
    map<ll, ll> mp;
    for (ll i = 2; i*i <= n; i++) {
        while (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }

    if (n > 1) {
        mp[n]++;
    }

    return mp;
}

// 文字列に "hoge" が含まれているか
// string str = "hogepiyo";
// if (str.find("hoge") != string::npos) {
//     cout << "文字列が含まれています" << endl;
// }

// char to string
// char c = 'a';
// string str = {c};

void solve(){
    int N;
    cin >> N;

    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (to_string(i).size() % 2 == 1)
            ans++;
    }

    cout << ans << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <iomanip>
#include <cmath>

#define vi vector<int>
#define tests int t; cin>>t; while(t--)
#define ll unsigned long long
#define vll vector<long long>
#define srt(v) sort(v.begin(), v.end())
#define srtg(v) sort(v.begin(), v.end(), greater<int> ())
#define FOR(k, n) for(int k=0; k<n; k++)



using namespace std;

char nums[10] = { '0','1','2','3','4','5','6','7','8','9' };
char alphsl[26] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };
const ll MOD = 1000000007;
char alphs[26] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };

ll ind(char c) {
    ll i = 0;
    while (c != nums[i]) i++;
    return i;
}

ll sttoin(string s) {

    int n = s.length();
    ll ans = 0, curr = 1;
    for (int i = n - 1; i > -1; i--) {
        ans += curr * ind(s[i]);
        curr *= 10;
    }
    return ans;
}

void solve() {

    string s;
    cin>>s;
    string t;
    cin>>t;
    int cnt=0;
    for(int i=0; i<s.length(); i++){
        if(s[i]!=t[i]) cnt++;
    }
    
    cout<<cnt<<endl;

}


int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    
        solve();



    return 0;
}

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

Measured memory_bytes: 256
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N=int(input())


a = 1
ans = 0
for i in range(N):
    ans += a
    a += 1

print(ans)


Measured memory_bytes: 13552
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef struct {
	int to;
	int D;
	int E;
} Edge;

class State {
public:

	int now;
	int money;
	int damaged;

	State(int now, int money, int damaged) {
		this->now = now;
		this->money = money;
		this->damaged = damaged;
	}

};

const int INF  = 999999;

vector<Edge> G[101];

int d[101][101];

int N, M, L;

int toV(int n, int l) {
	return n * L + l;
}

int main() {
	while (cin >> N >> M >> L, N + M + L != 0) {
		queue<State> q;
		for (int i = 0; i < 101; i++) {
			G[i].clear();
			for (int j = 0; j < 101; j++) {
				d[i][j] = INF;
			}
		}
		for (int i = 0; i < M; i++) {
			int A, B, D, E;
			cin >> A >> B >> D >> E;
			Edge e { B, D, E };
			Edge e2 { A, D, E };
			G[A].push_back(e);
			G[B].push_back(e2);
		}
		q.push(State(1, L, 0));
		while (!q.empty()){
			State s = q.front();
			q.pop();
			if (s.damaged >= d[s.now][s.money]) continue;
			d[s.now][s.money] = s.damaged;
			
			for (Edge e : G[s.now])
			{
				q.push(State(e.to, s.money, s.damaged + e.E));
				if (s.money - e.D >= 0) {
					q.push(State(e.to, s.money - e.D, s.damaged));
				}
			}
		}
		int m = INF;
		for (int i = 0; i <= L; i++) {
			m = min(m, d[N][i]);
		}
		cout << m << endl;
	}
	return 0;
}

Measured memory_bytes: 19740
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:

        # 全ての点に到達している場合
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            # 現在地を書き込む
            visited[j] = True
            # 次の点に移動する        
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)

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

pair< int, int > cal[1000000 + 10];
#define h first
#define w second

pair< int, bool > state[1000000 + 10];
#define la first
#define ri second

int map[1000 + 5][1000 + 5];

#define LIMT 1001000

int main()
{
	int lh, lw;
	int i, j;

	cin >> lh >> lw;

	for (i = 0; i <= lw + 1; i++)
	{
		map[0][i] = LIMT;
		map[lh + 1][i] = LIMT;
	}
	for (i = 1; i <= lh; i++)
	{
		map[i][0] = LIMT;
		map[i][lw + 1] = LIMT;
	}

	for (i = 1; i <= lh; i++)
	{
		for (j = 1; j <= lw; j++)
		{
			cin >> map[i][j];

			cal[map[i][j]].h = i;
			cal[map[i][j]].w = j;
		}
	}


	int cnt = 0;

	int mh[] = {1,0,-1,0};
	int mw[] = {0,1,0,-1};
	int nh, nw;
	bool flg1 = true;
	int tol;
	for (i = 1; i <= lh*lw; i++)
	{
		nh = cal[i].h;
		nw = cal[i].w;

		flg1 = true;

		for (j = 0; j < 4; j++)
		{
			if (map[nh][nw] > map[nh + mh[j]][nw + mw[j]])
			{
				if (state[map[nh + mh[j]][nw + mw[j]]].ri)
				{
					state[map[nh][nw]].ri = true;
					break;
				}

				if (flg1)
				{
					tol = state[map[nh + mh[j]][nw + mw[j]]].la;
				}

				flg1 = false;

				if (tol != state[map[nh + mh[j]][nw + mw[j]]].la)
				{
					state[map[nh][nw]].ri = true;
					break;
				}
			}
		}


		if (flg1)
		{
			state[map[nh][nw]].la = map[nh][nw];
		}

		else if (j == 4)
		{
			state[map[nh][nw]].la = tol;
		}

		if (state[map[nh][nw]].ri)
		{
			cnt++;
		}
	}


	/*
	cout << "\n\n";
	for (i = 1; i <= lh; i++)
	{
		for (j = 1; j <= lw; j++)
		{
			cout << state[map[i][j]].ri;
		}
		cout << "\n";
	}
	cout << "\n\n";
	*/


	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 22648