akhauriyash/Code-Regression huggingface dataset:
def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    a = set(a)
    ans[0] = 1
    ans[1] = 0 if 1 in a else 1
    num = 1000000007
    for i in range(2, n + 1):
        if i in a:
            continue
        ans[i] += (ans[i - 2] + ans[i - 1]) % num
    return str(ans[-1])


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))


Measured memory_bytes: 15592
#include <stdio.h>

int main(){
  int setsize;
  int b, c, tmp;
  int i, j, k;
  int isSuccess;

  scanf("%d", &setsize);
  for(i=0; i<setsize; i++){
    isSuccess=1;
    b=0; c=0;
    for(j=0; j<10; j++){
      scanf("%d", &tmp);
      if(b>tmp && c>tmp){
        isSuccess=0;
        for(k=j+1; k<10; k++) scanf("%d", &tmp);
        break;
      }
      else if(b>tmp) c=tmp;
      else if(c>tmp) b=tmp;
      else {
        if(b<c) c=tmp;
        else b=tmp;
      }
    }
    if(isSuccess) printf("YES\n");
    else printf("NO\n");
  }

  return 0;
}

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

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

  int one = 0;
  for (size_t i = 0; i < S.size(); ++i) {
    if (S[i] != '1') {
      break;
    }
    ++one;
  }

  if (K <= one) {
    cout << 1 << endl;
  } else {
    cout << S[one] << endl;
  }
}


Measured memory_bytes: 3592
import sys
from pprint import pprint

def solve(n):
    for i in range(1, 10):
        for j in range(1, 10):
            if n == i*j:
                print("Yes")
                return
    print("No")

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    solve(n)

Measured memory_bytes: 38256
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))



def main():
    a,b,c,k = na()
    if k <= a:
        print(k)
    elif k <= a+b:
        print(a)
    else:
        print(a-(k-(a+b)))
    return


if __name__ == '__main__':
    main()

Measured memory_bytes: 61728
#include <bits/stdc++.h>
#define int long long
#define all(a) (a).begin(),(a).end()
using namespace std;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n , k;
    cin >> n >> k;
    int arr[n];
    for(int& i : arr)
        cin >> i;
    
    sort(arr,arr+n);
    cout << accumulate(arr,arr+k,0ll) << endl;
        
    return 0;
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
typedef pair<int,int> pii;
#define ITR(v,c) for(auto v=begin(c);v!=end(c);v++)
#define FOR(v,a,n) for(int v=a;v<(int)(n);v++)
#define FORE(x,arr) for(auto &x:arr)
#define REP(v,n) FOR(v,0,n)
#define RREP(v,n) for(int v=(int)(n);v>=0;v--)
#define ALL(c) begin(c),end(c)
const int DX[4]={0,1,0,-1}, DY[4]={-1,0,1,0};
const int INF = 1e9;
const ll INFLL = 1e18;
template<class T,class U>ostream&operator<<(ostream &os,const pair<T,U> &p){
    os<<"("<<p.first<<","<<p.second<<")";return os;}
template<class T>ostream&operator<<(ostream &os,const vector<T> &v){
    ITR(i,v)os<<*i<<(i==end(v)-1?"":" ");return os;}
//------------------------------------------------------------------------------

signed main() {
    int H,W;
    cin>>H>>W;
    vector<vector<bool>> b(H),r(H);
    REP(i,H) {
        b[i].resize(W);
        REP(j,W) {
            if(i%2==1 && j==1) break;
            if(i%2==0 && j==W-1) break;
            b[i][j]=true;
        }
    }
    REP(i,H) {
        r[i].resize(W);
        REP(j,W) {
            if(i%2==0 && j==1) break;
            if(i%2==1 && j==W-1) break;
            r[i][W-j-1]=true;
        }
    }

    REP(i,H) {
        string s;
        cin>>s;
        REP(j,W) {
            if(s[j]=='#') {
                if(b[i][j]) r[i][j]=true;
                if(r[i][j]) b[i][j]=true;
            }
        }
    }

    REP(i,H) {
        REP(j,W) {
            putchar(b[i][j]?'#':'.');
        }
        putchar('\n');
    }
    putchar('\n');
    REP(i,H) {
        REP(j,W) {
            putchar(r[i][j]?'#':'.');
        }
        putchar('\n');
    }
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
#define fast        ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define filein      freopen("input.txt","r",stdin)
#define fileout     freopen("output.txt","w",stdout)
#define ll          long long
#define pii         pair<int,int>
using namespace std;

int main(){
    fast;

    int n;
    cin>>n;
    int arr[n+2];
    for(int i=0;i<n;i++) cin>>arr[i];
    sort(arr,arr+n);
    cout<<arr[n/2]-arr[n/2-1]<<endl;
}


Measured memory_bytes: 640
//                             In The Name Of Allah                                           
//                             	Mohammad Hosseini
#include <bits/stdc++.h>
#define	ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define int long long
#define ld long double
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std; 

const int N = 3e5 + 100, OO = 724249387, T = 1e6 + 100, M = 1e9 + 7, P = 6151, SQ = 280, lg = 30;
typedef pair <int, int> pii;

vector <int> v[N];
int dfs(int x, int y, int d, int top) {
	int ans = 0;
	if(d <= top) 
		ans++;
	for(auto u : v[x]) 
		if(u != y) 
			ans += dfs(u, x, d + 1, top);
	return ans;
}

int32_t main() {
	use_fast;
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	int ans = 0;
	if(k % 2) {
		for(int i = 1; i <= n; ++i) {
			vector <int> tp, bt;
			for (int u : v[i]) {
				tp.pb(dfs(u, i, 1, k / 2 + 1));
				bt.pb(dfs(u, i, 1, k / 2));
			}
			int su = 0;
			for (int x : bt) 
				su += x;
			int in = 0;
			for(int i = 0; i < (int)tp.size(); i++) 
				in = max(in, tp[i] - bt[i]);
			ans = max(ans, in + su + 1);
		}
	}
	else {
		for (int i = 1; i <= n; ++i) {
			int h = 1;
			for (auto u : v[i]) 
				h += dfs(u, i, 1, k / 2);
			ans = max(ans, h);
		}
	}
	cout << n - ans << endl;
	return 0;
}
/*
be carefull :
1- if not solve after 20 min, read again twice
2- after submit read the code again
3- fun with contest
4- uploaded by ubuntu 20.04 
5- ...
*/


Measured memory_bytes: 10788
#include <stdio.h>

int main()
{
   long long h,n,i;
   scanf("%lld %lld",&h,&n);
   if((1<=h<=1000000000)&&(1<=n<=100000)){
       long int a[n];
       for(i=0;i<n;i++){
           scanf("%ld",&a[i]);
           h=h-a[i];
       }
       if(h<=0)printf("Yes");
       else printf("No");
   }

    return 0;
}


Measured memory_bytes: 896
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define outl(x) cout<< (x) << '\n'
#define fi first
#define se second
using pii = pair<int,int>;
using ll = long long;
using vi = vector<int>;

int V, E;
vi G[100010];
int indeg[100010];

void topologicalSort(vi &ans)
{
    memset(indeg, 0, sizeof(indeg));
    ans.reserve(V+1);

    rep(i, V) {
        for (const auto &to : G[i]) {
            ++indeg[to];
        }
    }

    {
        queue<int> que;
        rep(i, V) {
            if (indeg[i] == 0) que.push(i);
        }

        while ( !que.empty()) {
            int u = que.front(); que.pop();
            ans.push_back(u);
            for (const auto &e: G[u]) {
                --indeg[e];
                if (indeg[e] == 0) que.push(e);
            }
        }
    }
    return;
}


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

    cin >> V>> E;

    rep(i, E) {
        int s, t;
        cin >> s >> t;
        G[s].push_back(t);
    }

    topologicalSort(ans);

    for (const auto &e: ans)
        outl(e);

    return (0);
}




Measured memory_bytes: 6292
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using BigInt = long long;
#define ALL(a)  (a).begin(),(a).end()

double getTemp(int x, int T) {
    return (T - (double)x * 0.006);
}


int main(){
    int N, T, A;
    cin >> N;
    cin >> T >> A;
    vector<int> H(N);
    rep(i, N) cin >> H[i];
    double a = 1000000;
    double b;
    int ans_idx;
    rep(i, N) {
        b = abs(A - getTemp(H[i], T));
        if (a > b){
            ans_idx = i + 1;
            a = b;
        }
    }
    cout << ans_idx << endl;
} 


Measured memory_bytes: 3608
#include<stdio.h>

int main(void)
{
    int a=0,n,i,s=0,p,max=0;

    scanf("%d",&n);
    for(i=0;i<n;i++){
       scanf("%d",&p);
       if (p>max) max=p;
       a=a+p;
    }
    s=a-max/2;
    printf("%d\n",s);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
#define pb push_back

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;
const double PI = acos(-1.0);


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * g / b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
map<ll, ll> prime_factor(ll n) {
	map<ll, ll> ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}



const int MAX_N = 100010;

// dp[i] := 体力をi減らした時の消費する魔力の最小値
int dp[10010];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int h, n; cin >> h >> n;
	VE a(n), b(n);
	rep(i, n) {
		cin >> a[i] >> b[i];
	}
	rep(i, 10010)dp[i] = INF;
	dp[0] = 0;
	rep(i, n) {
		for (int j = 0; j < a[i]; j++) {
			chmin(dp[j], b[i]);
		}
		for (int j = a[i]; j <= h + 1; j++) {
			chmin(dp[j], dp[j - a[i]] + b[i]);
		}
	}
	cout << dp[h] << endl;
	return 0;
}

Measured memory_bytes: 384
A, B, C, D, E, F = map(int, input().split(' '))

max_sugar = 0
max_water = 100*A
max_conc = 0.0
A_limit = F // (100*A)
for i in range(A_limit + 1):
    B_limit = (F-100*A*i) // (100*B)
    for j in range(B_limit + 1):
        if i == 0 and j == 0:
            continue
        sugar_limit = min(E * (A*i+B*j), F-100*(A*i+B*j))

        sugar_ = 0
        for c in range(sugar_limit//C + 1):
            d = (sugar_limit-c*C)//D
            temp_sugar = c*C + d*D
            sugar_ = max(sugar_, temp_sugar)
        temp_conc = sugar_/(sugar_+100*(A*i+B*j))
        if temp_conc > max_conc:
            max_conc = temp_conc
            max_water = 100*(A*i + B*j)
            max_sugar = sugar_
print('{0} {1}'.format(max_water+max_sugar, max_sugar))

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

int main() {
  int a, b;
  cin >> a >> b;
  vector<bool> B(4, true);
  B[a] = false;
  B[b] = false;
  for(int i = 1; i < 4; i++) {
     if(B[i]) {
       cout << i << endl;
       return 0;
     }
  }
  
}

Measured memory_bytes: 256
n=int(input())
s=input()
result=0
d={"RW":0,"WR":0}
for i in range(n):
    if s[i]=="R":
        result+=1
        d["RW"]+=1
        
for i in range(n):
    if s[i]=="R":
        d["RW"]-=1        
    else:
        d["WR"]+=1
    maximum,minimum=max(d["RW"],d["WR"]),min(d["RW"],d["WR"])
    sub_result=maximum
    result=min(sub_result,result)
print(result)



Measured memory_bytes: 67936
def solve():
    k, a, b = map(int,input().split())

    ans = k + 1  # hit every time

    if a+1 < b:    # exchange benefits
        u = k-a+1  # remaining steps after hitting A times

        # After hitting A times,
        # make B-A biscuits is produced every 2 steps
        # if u is odd, hit one at the last step.
        ans = a + u//2*(b-a) + u%2
    print(ans)


solve()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int inf = 1e9;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, b, a) for (int i = a - 1; i >= b; i--)
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dxx[8] = {1, 1, 1, 0, 0, -1, -1, -1}, dyy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

bool cmp (pint a, pint b) { return a.second < b.second; }
int main() {
    int n, m;
    cin >> n >> m;
    pint p[m];
    rep (i, 0, m) cin >> p[i].first >> p[i].second;
    sort (p, p + m, cmp);
    int ans = 0, end = 0;
    rep (i, 0, m) {
        if (p[i].first >= end) {
            end = p[i].second;
            ans++;
        }
    }
    cout << ans << "\n";
}


Measured memory_bytes: 4340
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll mod=1e9+7;
ll inf=1e10;

int main(){
  ll N,A[100000],B[100000];
  cin>>N;
  for (ll i(0);i<N;i++) cin>>A[i]>>B[i];
  ll l(0);
  ll ans(0);
  for (ll i(N-1);i>=0;i--){
    ll Aa = (A[i]+l+B[i]-1)/B[i]*B[i];
    l = Aa - A[i];
    ans+=Aa - A[i]-ans;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;

const string YES = "Yes";
const string NO = "No";

void solve(long long N, long long M, std::vector<long long> A){
    sort(ALL(A));
    ll sum = 0; REP(i, N) sum+=A[i];
    ll cnt=0;
    REP(i, N){
        if(A[i] * 4 * M >= sum) cnt++;
    }
    if(cnt >= M) cout<<YES<<endl;
    else cout<<NO<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, M, std::move(A));
    return 0;
}


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

int main() {

    int H, N;
    cin >> H >> N;

    vector<int> A(N);
    rep(i, N) cin >> A[i];

    int ans = 0;
    rep(i, N) {
        ans += A[i];
    }

    if (ans < H)
        cout << "No";
    else
        cout << "Yes";

    cout << endl;

    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
int main()
{
    long long int A,B;
    char C;

    scanf("%lli %c %lli", &A , &C, &B);

    if(C=='+')
        printf("%d\n",A+B);
    else if(C=='-')
        printf("%d\n",A-B);
        else
            return;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int a = sc.nextInt();
	int b = sc.nextInt();
	int area = a*b;
	int length = 2*a +2*b;
        System.out.println(area +" "+length);
    }
}

Measured memory_bytes: 26092
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2") //Enable AVX

#include <bits/stdc++.h>
#define db(x) cout << (x) << '\n';
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
typedef pair<double,ll> pdi;
typedef pair<ld,ld> pdd;
typedef pair<double,ll> pdi;
typedef pair<double,pii> pdp;
typedef pair<string,ll> psi;
typedef pair<ll,string> pls;
typedef pair<string,string> pss;
typedef pair<ll,pii> pip;
typedef pair<pii,pii> ppp;
typedef complex<ld> point;
typedef pair<point,int> ppi;
#define mod (ll)(1e9+7)
#define eps (1e-9)
#define oo (ll)(0x3f3f3f3f)
#define pi acos(-1)
#define MAXN (ll)(1e3+5)

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

    ll n;
    cin >> n;
    ll res=(n+2)*(n+1)*(n)/6;
    for(int i=0;i<n-1;i++)
    {
        ll u,v;
        cin >> u >> v;
        if(u>v)
            swap(u,v);
        res-=u*(n-v+1);
    }
    db(res)

    return 0;
}
/**
10
5 3
5 7
8 9
1 9
9 10
8 4
7 4
6 10
7 2
**/


Measured memory_bytes: 3648
#include<stdio.h>
int main(){
int i,n;
scanf("%d",&n);
int answer[n];
for(i=0;i<n;i++){
scanf("%d ",&answer[i]);
}
for(i=0;i<n;i++){
printf("%d",answer[n-1-i]);
if(i!=n-1) printf(" ");
}
printf("\n");
return 0;
}

Measured memory_bytes: 604
def sumDigit(str_digit):
    a = [int(n) for n in list(str(str_digit))]
    return sum(a)

n, a, b = map(int, input().split())
ans = 0
for i in range(n + 1):
    current = sumDigit(i)
    if a <= current <= b:
        ans += i
        # print('ans = ', ans)

print(ans)

Measured memory_bytes: 3060
//#pragma GCC optimize("-Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2")  //Enable AVX
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//order_of_key(x) : number of items less than x
//find_by_order(x) : iterator to x

#define mem(dp,a)           memset(dp,a,sizeof dp)
#define rep(i,a,b)          for(ll i=a;i<b;i++)
#define pb(x)               push_back(x)
#define mp(x,y)             make_pair(x,y)
#define fastio              ios_base::sync_with_stdio(false);cin.tie(NULL)
#define F                   first
#define S                   second
#define all(v)              (v).begin(),(v).end()

const ld pi=3.14159265359;
ll INF=1e18+10;
ll MOD=998244353;
ll mod=1e9+7;

inline ll add(ll a,ll b,ll m){
    if((a+b)>=m)return (a+b)%m;
    return a+b;
}

inline ll mul(ll a,ll b,ll m){
    if((a*b)<m)return a*b;
    return (a*b)%m;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    string s;cin>>s;
    ll dp[680][3][2];mem(dp,0);
    int n=s.length();
    bool cpar=0;
    ll ans=0;
    rep(i,0,n){
        dp[s[i]-'0'][(s[i]-'0')%3][1-cpar]=1;
        rep(j,0,680){
            bool npar = 1-cpar;
            int nval = j*10 + s[i]-'0';
            int nval6 = nval%673;
            for(int k=0;k<3;k++)
                dp[nval6][(k*10 +s[i]-'0')%3][npar]+=dp[j][k][cpar];
        }
        ans+=dp[0][0][1-cpar];
        rep(j,0,680)
            rep(k,0,3)
                dp[j][k][cpar]=0;
        cpar = 1-cpar;
    }
    cout<<ans;
}


Measured memory_bytes: 3792
#coding: UTF-8

# 指定した数以下の素数の個数を返却する
# 素数判定はエラストテネスのふるい

# 要素1000000のリスト（素数かどうかのリスト）を準備
max_number = 1000000
prime_flag_list = [True] * max_number

# 0、1は素数でない
prime_flag_list[0] = False
prime_flag_list[1] = False

# 2の倍数（2を除く）は素数でない
prime_flag_list[4::2] = [False] * len(prime_flag_list[4::2])

# 3以上の数について、素数ならその倍数を振るい落とす
for i in range(3, int(max_number**0.5) + 1, 2):
    prime_flag_list[i*i::i] = [False] * len(prime_flag_list[i*i::i])

# フラグの立ったままの箇所は素数なので、そこだけ取り出す
prime_list = [i for i in range(2, max_number) if prime_flag_list[i]]

while True:
    try:
        input = int(raw_input())
    except EOFError:
        break
    for i in range(0, len(prime_list)):
        if prime_list[i] > input:
            print i
            break
    if i >= len(prime_list) - 1:
        print len(prime_list)

Measured memory_bytes: 44448
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b,a%b);
}
/*配列Aに含まれる要素の異なる数字毎にカウントし、奇数個ある数字の個数が答え*/
int main() {
 int N;
 cin >> N;
 vector<int> d(N);
 for(int i = 0;i<N;i++){
	 cin >> d[i];
 }
 int ans = 0;
 for(int i = 0;i<N;i++){
	 for(int j = i+1;j<N;j++){
    ans += d[i] * d[j];
	 }
 }
cout << ans << endl;

}

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

int main(){
  int A,B,C,flag=0;
  scanf("%d%d%d",&A,&B,&C);
  if((A==B)&&(A!=C)) flag=1;
  if((B==C)&&(B!=A)) flag=1;
  if((A==C)&&(A!=B)) flag=1;
  if(flag==1){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}

Measured memory_bytes: 128
A,B = map(int,input().split())
cnt = 0
grid = []

for i in range(50):
    s = ''
    for j in range(25):
        k = 0
        if i%2 == 0 and cnt < A-1:
            s += '.###'
            cnt += 1
            k = 1
        if i%2 == 1 and cnt < A-1:
            s += '##.#'
            cnt += 1
            k = 1
        if k == 0:
            s += '####'
    grid.append(s)
s = ''
for i in range(100):
    s += '.'
grid.append(s)
cnt = 0
for i in range(49):
    s = ''
    for j in range(25):
        k = 0
        if i%2 == 0 and cnt < B-1:
            s += '#...'
            cnt += 1
            k = 1
        if i%2 == 1 and cnt < B-1:
            s += '..#.'
            cnt += 1
            k = 1
        if k == 0:
            s += '....'
    grid.insert(50,s)

print(100,100)
for i in range(100):
    print(grid[i])

Measured memory_bytes: 3064
import qualified Data.ByteString.Char8 as BS

main = BS.getLine >> BS.getLine >>= print . compute

-- 先頭から、文字が変わる度に++していく

compute :: BS.ByteString -> Int
compute s = fst $ BS.foldl' step (1,BS.head s) s

step :: (Int,Char) -> Char -> (Int,Char)
step (i,c) x
  | c == x = (i,c)
  | True   = (succ i, x)


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

using namespace std;
using ll = long long;

//container util
#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)

//print
#define pv(val) cerr << #val << '=' << (val) << endl

const int INF = 1e9;

int main(void){

	int N; cin >> N;
	vector<int> a(3*N);
	REP(i,3*N) cin >> a[i];

	SORT(a);
	ll ans = 0;
	REP(i,N) ans += a[3*N-2*(i+1)];

	cout << ans << endl;






	return 0;

}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 1003;
int n,m,a,b;
int ans[N][N];

int main(){
    scanf("%d %d %d %d",&n,&m,&a,&b); swap(a,b);
    rep(i,1,a) rep(j,1,b) ans[i][j]=0;
    rep(i,a+1,n) rep(j,1,b) ans[i][j]=1;
    rep(i,1,a) rep(j,b+1,m) ans[i][j]=1;
    rep(i,a+1,n) rep(j,b+1,m) ans[i][j]=0;
    rep(i,1,n) rep(j,1,m){
        printf("%d",ans[i][j]);
        if(j==m) puts("");
    }
    return 0;
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool g[705][705];
int color[705];
int n, m, a, b;
int cc[2];
int dp[2][705];

bool dfs(int u, int c){
	color[u] = c;
	cc[c]++;
	for(int v=1;v<=n;v++){
		if(g[u][v] == 0 && u != v){
			if(color[v] == -1){
				if(!dfs(v, 1-c)) return 0;
			}
			else if(color[u] == color[v]) return 0;
		}
	}
	return 1;
}
int main(){
	memset(dp, -1, sizeof(dp));
	memset(color, -1, sizeof(color));
	scanf("%d%d", &n, &m);
	for(int i=0;i<m;i++){
		scanf("%d%d", &a, &b);
		g[a][b] = g[b][a] = 1;
	}
	int mx = 0;
	int pv = 0, nt = 1;
	dp[0][0] = 0;
	for(int i=1;i<=n;i++){
		if(color[i] == -1){
			cc[0] = cc[1] = 0;
			if(!dfs(i, 0)) return !printf("-1\n");

			memset(dp[nt], -1, sizeof(dp[nt]));
			for(int j=0;j<=n;j++){
				if(dp[pv][j] == -1) continue;
				dp[nt][j+cc[0]] = dp[pv][j] + cc[1];
				dp[nt][j+cc[1]] = dp[pv][j] + cc[0];
			}
			swap(pv, nt);
		}
	}
	int ans = 1e9;
	for(int i=0;i<=n;i++){
		if(dp[pv][i] != -1){
			int e0 = i*(i-1)/2;
			int e1 = dp[pv][i]*(dp[pv][i]-1)/2;
			ans = min(ans, e0+e1);
		}
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 896
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;

public class Main
{
	static final int MAX_X = 8;
	static final int MAX_Y = 8;
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		String s;
		do
		{
			int[][] map = new int[MAX_Y+1][MAX_X+2];
			for (int i=0; i<MAX_Y; i++) {
				s = br.readLine();
				for(int j=1; j<MAX_X+1; j++)
					map[i][j] = Integer.parseInt(s.charAt(j-1)+"");
			}
			System.out.println(figure(map));
		} while((s=br.readLine())!=null && s.isEmpty());
	}
	private static char figure(int[][] map)
	{
		for (int i = 0; i < MAX_Y; i++) {
			for (int j = 1; j < MAX_X+1; j++) {
				if(map[i][j]==1){
					if(map[i+1][j] == 1 && map[i][j+1]==1){
						if(map[i+1][j+1]==1)	return 'A';
						else 					return 'G';
					} else if(map[i+1][j] == 0 && map[i][j+1]==1){
						if(map[i+1][j+1]==1)	return 'E';
						else 					return 'C';						
					} else {
						if(map[i+1][j+1]==1)		return 'F';
						else if (map[i+1][j-1]==1)	return 'D';	
						else 						return 'B';
					}
				}
			}
		}
		return '0';
	}
}

Measured memory_bytes: 9780
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 100005
#define INF 1000000005LL
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll X,K,Q;
ll r[SIZE];
ll A[SIZE],B[SIZE],a[SIZE],b[SIZE];

int main()
{
	cin >> X >> K;
	rep(i,1,K+1) cin >> r[i];
	A[0] = a[0] = 0LL;
	B[0] = b[0] = X;
	int smstart = INF;
	ll same = -1LL;
	rep(i,0,K){
		ll l = r[i+1]-r[i];
		if(same != -1LL){
			if(i%2==0){
				same = max(same-l,0LL);
				a[i+1] = same;
			}else{
				same = min(same+l,X);
				a[i+1] = same;
			}
			continue;
		}
		if(i%2==0){
			if(a[i]-l>0){
				A[i+1]=A[i];B[i+1]=B[i];
				a[i+1]=a[i]-l;b[i+1]=b[i]-l;
			}else{
				if(A[i]+l-a[i]<B[i]){
					A[i+1]=A[i]+l-a[i];B[i+1]=B[i];
					a[i+1]=0LL;b[i+1]=b[i]-l;
				}else{
					same = 0LL;
					a[i+1] = same;
					smstart = i+1;
				}
			}
		}else{
			if(b[i]+l<X){
				A[i+1]=A[i];B[i+1]=B[i];
				a[i+1]=a[i]+l;b[i+1]=b[i]+l;
			}else{
				if(B[i]-(l+b[i]-X)>A[i]){
					A[i+1]=A[i];B[i+1]=B[i]-(l+b[i]-X);
					a[i+1]=a[i]+l;b[i+1]=X;
				}else{
					same = X;
					a[i+1] = same;
					smstart = i+1;
				}
			}
		}
	}
	cin >> Q;
	rep(i,0,Q){
		ll t,c;
		cin >> t >> c;
		int idx = upper_bound(r,r+K+1,t) - r;
		idx--;
		ll d;
		if(idx >= smstart){
			d = a[idx];
		}else{
			if(c <= A[idx]){
				d = a[idx];
			}else if(c >= B[idx]){
				d = b[idx];
			}else{
				d = a[idx] + (c - A[idx]);
			}
		}
		t -= r[idx];
		if(idx%2==0){
			d = max(d-t,0LL);
		}else{
			d = min(d+t,X);
		}
		cout << d << endl;
	}
	return 0;
}


Measured memory_bytes: 5120
#include <iostream>
#include <iomanip>

using namespace std;

int main() {

    int a, b, c, d;
    
    cin >> a;
    cin >> b;
    
    c = a * b;
    d = (a + b) * 2;
    
    cout << c << " " << d << endl;
    
    return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FPEN freopen("in.txt", "r", stdin);
#define debug(...)                                                             \
    { cerr << "# " << __VA_ARGS__ << "\n"; }
#else
#define debug(...)
#define FPEN
#endif
const int maxn = 200009;
typedef long long i64;
typedef pair<i64, i64> pi64;
typedef pair<int, int> pi;
const i64 MOD = 119 << 23 | 1;
class {
  public:
    void solve() {
        int s, w;
        cin >> s >> w;
        if (w >= s) {
            cout << "unsafe";
        } else {
            cout << "safe";
        }
    }
} NSPACE;
int main() {
    FPEN;
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    NSPACE.solve();
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)

#define mod (998244353)
ll ppow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if ((n & 1) == 1) {
            ans %= mod;
			ans = ans * x;
		}
		x = x * x;
        x %= mod;
		n >>= 1; 
	}
	return ans%=mod;
}
void solve()
{
    ll n;cin>>n;
    vector<ll>d(n,0);
    ll x,maxx=0;
    REP(i,n){
        cin>>x;
        maxx=max(maxx,x);
        d[x]++;
        if(i==0&&x!=0){cout<<0<<endl;return;}
    }
    if(d[0]!=1){cout<<0<<endl;return;}
    REP(i,maxx)if(d[i]==0){cout<<0<<endl;return;}
    ll Ans=1;
    REP(i,maxx){
        Ans*=ppow(d[i],d[i+1]);
        Ans%=mod;
    }cout<<Ans%mod<<endl;
}
int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    solve();
    return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define MOD 100000007
#define PI 3.141592653589793238
#define pb push_back
#define ALL(V) (V).begin(), (V).end()
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long long int lint;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
inline ll gcd(ll a, ll b) { return (a % b == 0 ? b : gcd(b, a % b)); }
inline ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
inline ll char_to_ll(char c) { return (int)(c - '0'); }
inline ll string_to_ll(string s) { return atoi(s.c_str()); }
inline bool is_prime(ll x){ if(x <= 1) return false; for(ll i = 2; sqrt(i) <= x; i++) if(x % i == 0) return false; return true; }

int main(){
    ll N, ans = 0;
    cin >> N;

    rep(i, 0, N + 1){
        if(i % 3 != 0 && i % 5 != 0) ans += i;
    }

    cout << ans << endl;

    return 0;
}


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

// iterator
#define REP(i,init, n) for(lli i=init;i<n;i++)
#define REPE(i,init, n) for(lli i=init;i<=n;i++)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) {cin1(x[i]);}
#define ncin2(n, x, y)      REP(i, 0, n) {cin2(x[i], y[i]);}
#define ncin3(n, x, y, z)   REP(i, 0, n) {cin3(x[i], y[i], z[i]);}

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define cout2(x, y)      cout << #x << ": " << x << ", " << #y << ": " << y << endl;
#define cout3(x, y, z)   cout << #x << ": " << x << ", " << #y << ": " << y << ", " << #z << ": " << z << endl;;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

#define coutp(p)         cout << #p << ":" <<  " (" << p.first << ", " << p.second << ")" << endl;

// sort
#define sort_r(x, y)        sort(x, y, greater<lli>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

typedef long long int lli;
typedef pair<lli, lli> P;
typedef tuple<lli, lli, lli> tup;

int main() {
    lli n;
    cin1(n);
    lli b[n-1];
    ncin1(n-1, b);
    lli ans = 0;
    ans += b[0];
    ans += b[n-2];

    REPE(i, 1, n-2) {
        ans += min(b[i-1], b[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n, x;
    
    
    while(cin >> n >> x){
        int ans = 0;
        if (n == 0 && x == 0) break;
        
        vector<int> v(n);
        for (int i = 0; i < n; i++) v[i] = i+1;
        
        
        for (int i = 0; i < n-2; i++){
            for (int j = i+1; j < n-1; j++){
                int c = x - v[i] - v[j];
                
                if(v[j] < c && c <= n) ans++;
            }
        }
        cout << ans << endl;
    }

}


Measured memory_bytes: 3100
N=int(input())
A=[]
for i in range(N):
  S=input()
  A.append(S)
ans=0
for i in range(N):
  x=0
  for j in range(N):
    for k in range(N):      
      if A[j][k-i]!=A[k][j-i]:
        x=1
  if x==0:
    ans+=1
print(ans*N)

Measured memory_bytes: 43628
#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++)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define cer(x) cerr << x <<endl
#define ALL(a) (a).begin(),(a).end()
#define MOD 1e9+7
typedef long long ll;
using namespace std;

string s;

int main()
{
	map<string, int> days;
	days["MON"] = 1;
	days["TUE"] = 2;
	days["WED"] = 3;
	days["THU"] = 4;
	days["FRI"] = 5;
	days["SAT"] = 6;
	days["SUN"] = 7;
	cin >> s;
	if (s == "SUN")co(7);
	else co(days["SUN"] - days[s]);
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, M;
  cin >> N >> M;
  vector<int> vec(M * 2);
  for (int i = 0; i < M * 2; i++) {
    cin >> vec.at(i) >> vec.at(i+1);
    i++;
  }
  
  vector<int> result(N);
  
  for (int i = 0; i < vec.size(); i++) {
    result.at(vec.at(i) - 1)++;
  }
  
  for (int i = 0; i < result.size(); i++) {
    cout << result.at(i) << endl;
  }
}

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

int main() {
  int N;
  cin >> N;
  int a1 = N / 1000;
  int a2 = N % 1000;
  int b1 = a2 / 100;
  int b2 = a2 % 100;
  int c1 = b2 / 10;
  int c2 = b2 % 10;
  
  if ( b1 == c1){
    if ( a1 == b1 || c1 == c2){
      cout << "Yes" <<  endl;
    } else {
      cout << "No" << endl;
    }
  } else {
    cout << "No" << endl;
  }
}

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

int main(){
	int N;
	cin >> N;
	string S;
	cin >> S;
	int ans = 0;
	bool check[2][26];
	for(int i=0;i<26;i++){
		check[0][i] = false;
		check[1][i] = false;
	}
	for(int i=1;i<N;i++){
		for(int j=0;j<i;j++){
			check[0][S[j] - 'a'] = true;
		}
		for(int j=i;j<N;j++){
			check[1][S[j] - 'a'] = true;
		}
		int count = 0;
		for(int i=0;i<26;i++){
			if(check[0][i] && check[1][i])count++;
		}
		ans = max(ans,count);
		for(int i=0;i<26;i++){
			check[0][i] = false;
			check[1][i] = false;
		}
	}
	cout << ans << endl;
}

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

int main() {
	int R,G,B,N,r=0;
	cin >> R >> G >> B >> N;

	rep(i,N/R+1)
		rep(j,(N-R*i)/G+1)
			if((N-R*i-G*j)%B == 0)
				++r;
	cout << r << endl;
}

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

int main() {
	int a[4] = {};
	int i;
	int n, m;
	for (i = 0; i < 3; i++) {
		std::cin >> n >> m;
		a[n - 1]++;
		a[m - 1]++;
	}
	n = 0;
	for (i = 0; i < 4; i++) {
		if (a[i] > 2) {
			std::cout << "NO";
			return 0;
		}
	}
	for (i = 0; i < 4; i++) {
		if (a[i] == 0) {
			std::cout << "NO";
			return 0;
		}
	}
	std::cout << "YES";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <climits>
#include <math.h>
#include <string.h>
using namespace std;
#pragma warning(disable : 4996)
typedef long long ll;
typedef unsigned long long ull;



int main() {
#ifdef _DEBUG
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)cin >> a[i];
	int ans = INT32_MAX;
	for (int i = 1; i <= 150; i++) {
		int cur = 0;
		for (int j = 0; j < n; j++) {
			cur += (a[j] - i) * (a[j] - i);
		}
		ans = min(ans, cur);
	}
	cout << ans;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b;
	if (a%2==0)
	{
		if (b%2==0)
		{
			ll t=(b-a)/2;
			if (t%2==0) cout<<(0^b);
			else cout<<(1^b);
		}
		else
		{
			ll t=(b-a+1)/2;
			if (t%2==0) cout<<"0";
			else cout<<"1";
		}
	}
	else
	{
		if (b%2==1)
		{
			ll t=(b-(a+1)+1)/2;
			if (t%2==0) cout<<(a^0);
			else cout<<(a^1);
		}
		else
		{
			ll t=((b-1)-(a+1)+1)/2;
			if (t%2==0) cout<<((a^0)^b);
			else cout<<((a^1)^b);
		}
	}
	return 0;
}

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

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    VL b(n + 1);
    b[0] = 0;
    FOR(i, 1, n) {
        ll a;
        cin >> a;
        b[i] = b[i - 1] + a;
    }

    map<ll, ll> mod_map;
    REP(i, n + 1) mod_map[b[i] % m]++;
    ll ans = 0;
    for(const auto& pair : mod_map) {
        if(pair.second > 1) ans += pair.second * (pair.second - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4992
#include <algorithm>
#include <iostream>
using namespace std;
int N,W;
int w[1000];
int c[1000];
char tmp;
int dp[1001];
int main() {
	int tc=1;
	while(cin>>W>>N){
		for(int i=0;i<N;i++){
			cin>>c[i]>>tmp>>w[i];
		}
		fill(dp+0,dp+W+1,0);
		for(int i=0;i<N;i++){
			for(int j=W;j>=0;j--){
				if(j+w[i]>W)continue;
				dp[j+w[i]]=max(dp[j+w[i]],dp[j]+c[i]);
			}
		}
		int mans=*max_element(dp,dp+W+1);
		for(int i=0;i<=W;i++){
			if(mans==dp[i]){
				cout<<"Case "<<tc++<<":"<<endl;
				cout<<mans<<endl;
				cout<<i<<endl;
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 0
using System;

namespace  ITP1_5_D
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            int i = 1;

            while(true)
            {
                int x = i;

                bool flag = false;

                if(x % 3 == 0)
                {
                    Console.Write(" {0}", i);
                    flag = true;
                }

                if(flag == false)
                {
                    while(true)
                    {
                        if(x % 10 == 3)
                        {
                            Console.Write(" {0}", i);
                            break;
                        }
                        x /= 10;
                        if(x == 0) break;
                    }
                }

                if((++i) > n) break;
            }

            Console.WriteLine();
        }
    }
}

Measured memory_bytes: 9384
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: usize,
        b: usize,
    }
    println!("{}", if a > b*2 {a - b * 2} else {0});
}


Measured memory_bytes: 4352
import java.util.*;
import java.io.*;
import java.text.*;
import java.math.*;
import static java.lang.Integer.*;
import static java.lang.Double.*;
import java.lang.Math.*;

public class Main {

	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	public void run() throws Exception {
		FastIO file = new FastIO();
		long n = file.nextLong();
		long ans = n * (n - 1) / 2;
		System.out.println(ans);
	}

	public static class FastIO {
		BufferedReader br;
		StringTokenizer st;

		public FastIO() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

	public static long pow(long n, long p, long mod) {
		if (p == 0)
			return 1;
		if (p == 1)
			return n % mod;
		if (p % 2 == 0) {
			long temp = pow(n, p / 2, mod);
			return (temp * temp) % mod;
		} else {
			long temp = pow(n, (p - 1) / 2, mod);
			temp = (temp * temp) % mod;
			return (temp * n) % mod;

		}
	}

	public static long pow(long n, long p) {
		if (p == 0)
			return 1;
		if (p == 1)
			return n;
		if (p % 2 == 0) {
			long temp = pow(n, p / 2);
			return (temp * temp);
		} else {
			long temp = pow(n, (p - 1) / 2);
			temp = (temp * temp);
			return (temp * n);

		}
	}

	public static long gcd(long x, long y) {
		if (x == 0)
			return y;
		else
			return gcd(y % x, x);
	}

	public static boolean isPrime(int n) {
		if (n <= 1)
			return false;
		if (n <= 3)
			return true;

		if (n % 2 == 0 || n % 3 == 0)
			return false;

		for (int i = 5; i * i <= n; i = i + 6)
			if (n % i == 0 || n % (i + 2) == 0)
				return false;

		return true;
	}
}


Measured memory_bytes: 21204
#include<iostream>
#include<math.h>
using namespace std;

int main(){
  long long X,Y,tmp;
  int ans;
  cin >> X >> Y;

  ans = 0;
  for(int i = 0;;i++){
    tmp = X*pow(2,i);
    //cout << tmp << endl;
    if(tmp <= Y) ans++;
    else break;
  }

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

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;
int n;

const int INF = 1 << 29;

typedef pair<int,int> P;
vector<P> teams;
bool sortSecond(const P& p1, const P& p2)
{
	if(p1.second != p2.second) return p1.second < p2.second;
	if(p1.first != p2.first) return p1.first < p2.first;
	return false;
}

int main(void)
{
	while(cin >> n && n)
	{
		teams.resize(n);
		for (int i = 0; i < n; i++)
		{
			teams[i] = P(0, i);
		}
		for (int i = 0, leags = n * (n - 1) / 2; i < leags; i++)
		{
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			if(c == d)
			{
				teams[a - 1].first++;
				teams[b - 1].first++;
			}
			else if(c > d) teams[a - 1].first += 3;
			else teams[b - 1].first += 3;
		}
		sort(teams.begin(), teams.end(), greater<P>());
		int hikiwake = 0;
		for (int i = 0; i < n; i++)
		{
			int tmp = teams[i].first;
			teams[i].first = i + 1 - hikiwake;
			if(i + 1 < n && tmp == teams[i + 1].first)
			{
				hikiwake++;
			}
			else hikiwake = 0;
		}
		sort(teams.begin(), teams.end(), sortSecond);
		for (int i = 0; i < n; i++)
		{
			cout << teams[i].first << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1200
#include <iostream>

using namespace std;

int func(int a, int b, int n)
{
  if(n == 0){
    return 0;
  }
  int u = 10*a;

  return (u/b + func(u%b, b, n-1));
}

int main()
{
  int n, a, b;

  while(cin >> a >> b >> n){
    a %= b;
    cout << func(a, b, n) << endl;
  }

  return 0;
}

Measured memory_bytes: 0
#include <iostream>

using namespace std;

int main()
{
	int A, B, C, max[100], i, k;
	cin >> A >> B >> C;
	for(i=1,k=0;i<=A and i<=B; i++)
	{
		if(A%i==0 and B%i==0)
		{
			max[k]=i;
			k++;
		}

	}
	cout << max[k-C] << endl;
	return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
y = 0
for x in range(1, 1001):
    y += x
    l.append(y/x)
m = []
for i in p:
    m.append(l[i-1])
s = [0]
z = 0
for i in m:
    z += i
    s.append(z)
ans = []
for i in range(n-k+1):
    ans.append(s[i+k] - s[i])
print(max(ans))

Measured memory_bytes: 78984
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,a,b,c,d,i=1,x,k,k1,k2,j=1,I,J;
    cin>>n>>a>>b>>c>>d;  
    if(n%a==0){
      k1=n/a;
    }
    else {
       k1=n/a+1;
    }
    if(n%c==0){
      k2=n/c;
    }
    else{
      k2=n/c+1;
    }
  if(k1*b==k2*d){
    cout<<k1*b<<endl;
  }
  else if(k1*b>k2*d){
    cout<<k2*d<<endl;
  }
  else {
    cout<<k1*b<<endl;
  }
  return 0;
}

      





Measured memory_bytes: 3112
#include<cstdio>
#include<vector>
#include<algorithm>
//#include<numeric>
#include<functional>
//#include<deque>
//#include<string>
//#include<iostream>

using namespace std;
const int one = 1;
const int big = (one<<30);
typedef long long int llint;
//11:10～13:00
int main(void){
	llint N,ans=0,i,a,gen;
	vector<llint> A;
	vector<llint> wa;//累積和
	scanf("%lld",&N);
	for(i=0;i<N;i++){
		scanf("%lld",&a);
		A.push_back(a);
	}
	sort(A.begin(),A.end());
	gen=0;
	for(i=0;i<N;i++){
		gen+=A[i];
		wa.push_back(gen);
	}
	for(i=N-2;i>=0;i--){
		if(2*wa[i]<A[i+1]){break;}
		ans++;
	}ans++;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 2548