akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <random>
#include <fstream>
#define rep(i, n) for (int i = 0; i < n; i++)
#define pi 3.14159265358979323846
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{
  ll r;
  while ((r = a % b))
  {
    a = b;
    b = r;
  }
  return b;
}

int main()
{

  int a,b; cin >> a >> b;
  cout << (a-1)*(b-1) << endl;

  return 0;
}


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

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

	int N;
	cin >> N;
	int a = N % 10;
	int b = (int)(N / 10) % 10;
	int c = (int)(N / 100) % 10;
	if (a == 7 || b == 7 || c == 7) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


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

int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  for (int i= 0; i < N; i++) {
    cin >> d.at(i);
  }
  sort(d.begin(), d.end());
  
  int count = 0;
  int tmp;
  for (int i = 0; i < N; i++) {
    if (tmp == d.at(i)) count++;
    tmp = d.at(i);
  }
  cout << N - count << endl;
}


Measured memory_bytes: 256
n = int(input())
A,B,C = [],[],[]
for i in range(n):
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)

dp = [[0]*3 for i in range(n+1)]
for i in range(n):
    dp[i+1][0] = max(max( dp[i][1], dp[i][2] ) + A[i] ,dp[i+1][0])
    dp[i+1][1] = max(max( dp[i][0], dp[i][2] ) + B[i] ,dp[i+1][1])
    dp[i+1][2] = max(max( dp[i][0], dp[i][1] ) + C[i] ,dp[i+1][2])
    
print(max(dp[-1]))


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

typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

const int mx=1e6+11;
const double PI = acos(-1);
#define MOD 1000000007

#define nl '\n'
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair

#define sz(x) x.size()
#define tt int t; cin>>t; while(t--)
#define be(a) (a).begin(),(a).end()
#define rbe(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a,b,sizeof(a))
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl

#define su ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define frac cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p )
{
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v )
{
    os << "{";
    for(auto it = v.begin(); it != v.end(); ++it)
    {
        if( it != v.begin() )
            os << ", ";
        os << *it;
    }
    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v )
{
    os << "[";
    for(auto it = v.begin(); it != v.end(); ++it)
    {
        if( it != v.begin() )
            os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename T >
ostream &operator << ( ostream & os, const multiset< T > &v )
{
    os << "[";
    for(auto it = v.begin(); it != v.end(); ++it)
    {
        if( it != v.begin() )
            os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v )
{
    os << "[";
    for(auto it = v.begin(); it != v.end(); ++it)
    {
        if( it != v.begin() )
            os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)

void faltu ()
{
    cerr << endl;
}

template <typename T>
void faltu( T a[], int n )
{
    for(int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}

template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest)
{
    cerr << arg << ' ';
    faltu(rest...);
}


int gcd(int a,int b)
{
    return b ? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
    return (a*( b/ gcd(a,b)));
}

void f()
{
    int a,b;
    cin>>a>>b;
    if(b%a)
        cout<<b-a<<nl;
    else
        cout<<a+b<<nl;
}

int main()
{
    su;
    f();
    return 0;
}


Measured memory_bytes: 3588
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1e9+7;
const llint big=(llint)(2.19e15+1);
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int main(void){
	while(-1){
		int h,w,j,i;cin>>h>>w;
		if(h+w==0){RE;}
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				if(0<i&&i<h-1&&0<j&&j<w-1){cout<<'.';}
				else{cout<<'#';}
			}
			cout<<endl;
		}
		cout<<endl;
	}
	RE;
}


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

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;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        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() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

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

public class Main {
    static int[] w = new int[100010];
    static int[] v = new int[100010];
    static int[][] dp = new int[110][100010];
    static int k;

    static int chmin(int a, int b) {
        if (a > b) {
            a = b;
            return a;
        }
        return a;
    }

    static int chmax(int a, int b) {
        if (a < b) {
            a = b;
            return a;
        }
        return a;
    }

    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        double a = fs.nextDouble();
        double b = fs.nextDouble();

        System.out.println((int) Math.round((a + b) / 2));
    }
}


Measured memory_bytes: 80076
#include <iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<ctime>
#include<functional>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<map>
#include<set>
#include<tuple>
#include<cassert>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iomanip>
#include<climits>
#include<typeinfo>
#include<utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(ll i=0;i<n;i++)
#define For(i,m,n) for(int i=m;i<n;i++)
#define FOR(i,m,n) for(ll i=m;i<n;i++)
double pi = 3.141592653589793238;
using ll = long long;
using namespace std;

ll LGCD(ll x, ll y) { if (x % y == 0) return y;else return LGCD(y, x % y); }
ll LLCM(ll x, ll y) { return x * y / LGCD(x, y); }

int GCD(int x, int y) { if (x % y == 0) return y;else return GCD(y, x % y); }
int LCM(int x, int y) { return x * y / GCD(x, y); }
ll dpcombination[10000][10000];

ll modi = 1000000007;
ll combination(ll n, ll r) {
	if (n == r) { return dpcombination[n][n] = 1; }
	else if (r == 0) { return dpcombination[n][0] = 1; }
	else if (r == 1) { return dpcombination[n][1] = n; }
	else if (dpcombination[n][r]) { return dpcombination[n][r]; }
	else { return dpcombination[n][r] = combination(n - 1, r - 1) % modi + combination(n - 1, r) % modi; }
}

void clockman(int time1) {

	cout << 1.0*(clock() - time1) / CLOCKS_PER_SEC << endl;
	return;
}
//cout << fixed << setprecision(10)

void printVec(std::vector<int> &vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

int main() {

	int n,k;
	cin >> n >> k;
	vector<int>p(n);
	for (int i = 0;i < n;i++) {
		cin >> p[i];

	}
	sort(p.begin(), p.end());
	int ans = 0;
	for (int i = 0;i < k;i++) {
		ans = ans + p[i];
	}

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


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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    int a, b;
    string s;
    cin >> a >> b >> s;
    if (a+b+1 != s.size() or s[a] != '-') {
        cout << "No" << endl;
        return 0;
    }

    rep(i, a) {
        if ('0' <= s[i] and s[i] <= '9') {
            ;
        }
        else {
            cout << "No" << endl;
            return 0;
        }
    }

    for (int i=a+1; i < a+b+1; ++i) {
        if ('0' <= s[i] and s[i] <= '9') { ; }
        else {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define INF LLONG_MAX/3
#define eps LDBL_EPSILON
#define moder 1000000007
#define pie 3.141592653589793238462643383279
#define rep(i,n) for(int i=0;i<n;i++)
#define P std::pair<int,int>
#define prique priority_queue<int,vector<int>,greater<int>>
using namespace std;
int n,w;
int a[110],b[110];
int dp[110][100010];
signed main(){
	cin>>n>>w;
	rep(i,n)cin>>a[i]>>b[i];
	rep(i,n){
		rep(j,100010){
			if(j+a[i]<=w)dp[i+1][j+a[i]]=max(dp[i+1][j+a[i]],dp[i][j]+b[i]);
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
		}
	}
	int ans=0;
	rep(i,w+1){
		ans=max(ans,dp[n][i]);
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 79360
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define drep(i,n) for(ll i = (n)-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (ll)(x).size()
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
ll gcd(ll a,ll b){if(a%b==0){return b;}else{return(gcd(b,a%b));}}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int INF=1e9;
const ll MX = 1e18;
const int MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);
 
int main() {
  string s;
  cin>>s;
  int n=len(s);
  bool ja=true;
  string xs=s;
  reverse(all(xs));
  if(s!=xs) ja=false;
  string s1=s.substr(0,(n-1)/2);
  string xs1=s1;
  reverse(all(xs1));
  if(s1!=xs1) ja=false;
  string s2=s.substr((n+3)/2-1,(n-1)/2);
  string xs2=s2;
  reverse(all(xs2));
  if(s2!=xs2) ja=false;
  if(ja) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include<string>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=2*1e5+5;

int main()
{
    FAST

ll x;
cin>>x;
if(x%2==1)
    return cout<<0,0;
x/=2;
ll res=0;
while(x)
{
    res+=x/5;
    x/=5;
}
cout<<res<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main(void){
  int N;
  char S[100010];
  int i;
  scanf("%d",&N);
  scanf("%s",S);
  int a=1;
  for(i=1;i<N;i++){
    if(S[i]!=S[i-1]){
      a=a+1;
    }
  }
  printf("%d",a);
  return 0;
}

Measured memory_bytes: 2220
{-# LANGUAGE BangPatterns #-}

module Main
  ( main
  )
where

import           Control.Applicative
import           Control.Monad
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.List
import           Data.Maybe
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as MV
import           Control.Monad.ST
import           Data.Ord
import qualified Data.Vector.Unboxed           as UV

parse = fst . fromJust
parseInt = parse . BS.readInt
parseInteger = parse . BS.readInteger
readInt = parseInt <$> BS.getLine
readInteger = parseInteger <$> BS.getLine
readIntList = map parseInt . BS.words <$> BS.getLine
readIntegerList = map parseInteger . BS.words <$> BS.getLine

main = do
  a <- getLine 
  b <- getLine 
  c <- getLine
  putStrLn [solve 'a' a b c]

solve !crt !a !b !c
  | crt == 'a' = if null a then 'A' else solve (head a) (tail a) b c
  | crt == 'b' = if null b then 'B' else solve (head b) a (tail b) c
  | otherwise = if null c then 'C' else solve (head c) a b (tail c)


Measured memory_bytes: 508
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e15)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://atcoder.jp/contests/abc097/tasks/abc097_b

int main() {
    int X; cin >> X;
    vector<int> expo(X+5, 0);
    expo[1] = 1;
    REPS(b, 2, X+1) {
        int v = b * b;
        while(v <= X) {
            expo[v] = 1;
            v *= b;
        }
    }

    for (int i = X; i >= 0; i--) if (expo[i]){
            cout << i << "\n";
            return 0;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <list>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <cstring>
#include <cmath>
//#include<bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
const int SIZE=55;
const double EPS=1e-6;

int a[SIZE],n;

bool check(){
	for(int i=1;i<n;i++){
		if(a[i]<a[i-1]) return false;
	}
	return true;
}

int main(){
	/*main function start*/
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",a+i);
	}
	bool ok=false;
	if(check()) ok=true;
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			swap(a[i],a[j]);
			if(check()) ok=true;
			swap(a[i],a[j]);
		}
	}
	if(ok) puts("YES"); else puts("NO");
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
    new Main();
  }
  public Main() {
    try (Scanner sc = new Scanner(System.in)) {
      String S = sc.next();
      StringBuilder rev = new StringBuilder();
      for (int i = S.length() - 1;i >= 0;-- i) {
        rev.append(S.charAt(i));
        switch(rev.toString()) {
          case "maerd":
          case "remaerd":
          case "esare":
          case "resare":
            rev.delete(0, rev.length());
        }
        if (rev.length() >= 8) break;
      }
      System.out.println(rev.length() == 0 ? "YES" : "NO");
    }
  }
}


Measured memory_bytes: 32568
#include <bits/stdc++.h>
using namespace std;
#define repl(i, l, r) for (ll i = (l); i < (r); i++)
#define rep(i, n) repl(i, 0, n)
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define CST(x) cout << fixed << setprecision(x)
using ll = long long;
const ll MOD = 1000000007;
const int inf = 1e9 + 10;
const ll INF = 4e18 + 10;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	string s;
	cin >> s;
	int n = s.size();
	int cnt = 0;
	char c = s[0];
	rep(i, n) {
		if (s[i] != c) {
			cnt++;
			c = s[i];
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 512
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}
func fSum(a []float64) float64 {
	x := 0.
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	k := iScan()
	a := append([]int{0}, iSScan(n)...)
	for i := 1; i <= n; i++ {
		a[i] += a[i-1]
	}
	d := make(map[int]int)
	ans := 0
	for i := 0; i <= n; i++ {
		ans += d[(a[i]-i)%k]
		d[(a[i]-i)%k]++
		if i-k+1 >= 0 {
			d[(a[i-k+1]-(i-k+1))%k]--
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 15684
// {{{ Headers
// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}

#include <cassert>
#include <cctype>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#include <fstream>
#include <iostream>
#include <sstream>

using namespace std;
// }}}

typedef long long int64;
const int INF = 0x3f3f3f3f;
template <class T> inline int len (const T &a) { return a.size (); }
#define ALL(x) (x).begin(), (x).end()

const int MX = 100 * 1000 + 5;
int a [MX];
int dp [MX];

int
main () {
    int N;
    scanf ("%d", &N);
    for (int i = 0; i < N; i++) scanf ("%d", a + i);
    for (int i = 1; i < N; i++) {
        dp [i] = dp [i - 1] + abs (a [i] - a [i - 1]);
        if (i >= 2)
            dp [i] = min (dp [i], dp [i - 2] + abs (a [i] - a [i - 2]));
    }
    printf ("%d\n", dp [N - 1]);

#ifdef LOCALHOST
	cerr << "time: " << (int64) clock () * 1000 / CLOCKS_PER_SEC << " ms" << endl;
#endif
    return 0;
}



Measured memory_bytes: 1024
fun main(args: Array<String>) {
    while (true) {
        var s = readLine()!!.toString()
        if (s == "-") break
        val m = readLine()!!.toInt()
        val h = (0 until m).map { readLine()!!.toInt() }
        h.forEach { i ->
            s = s.slice(i until s.length) + s.slice(0 until i)
        }
        println(s)
    }
}


Measured memory_bytes: 24488
l,r=map(int,input().split())
if r-l>2019:
    print(0)
else:
    l1=l%2019
    r1=r%2019
    k=(r1*l1)%2019
    for i in range(l1,r1):
        for j in range(i+1,r1+1):
            if i*j%2019<k:
                k=i*j%2019
    print(k)

Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define clear(arr, val) memset(arr, val, sizeof(arr))

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

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };


int main()
{
	int n, q;
	while (cin >> n >> q, n | q)
	{
		int c[128];
		clear(c, 0);
		for (int i = 0; i < n; ++i)
		{
			int m, t;
			cin >> m;
			while (m--)
			{
				cin >> t;
				++c[t];
			}
		}

		int res = 0;
		int maxi = *max_element(c, c + 128);
		int t = find(c, c + 128, maxi) - c;
		if (maxi >= q)
			res = t;
		cout << res << endl;
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <stdio.h>
#include <cstring>

using namespace std;

int main()
{
	char a[101] = {0};
	char b[101] = {0};
	int check = 0;
	cin >> a >> b;
	
	int aa = strlen(a);
	int bb = strlen(b);
	
	if(aa > bb){

		cout << "GREATER";
		check = 1;
	}
	
	else if(aa < bb){
		
		cout << "LESS";
		check = 1;
	}
		
	else
		for(int i = 0; i < aa; i++){
		
			if(a[i] > b[i]){
				
				cout << "GREATER";
				check = 1;
				break;
			}
			
			else if(a[i] < b[i]){
				
				cout << "LESS";
				check = 1;
				break;
			}	
		}
	
	if(check == 0)
		cout << "EQUAL";
}






  
     
  


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

constexpr ll mod = 1000000007;
constexpr ll modsize = 0;
vector<ll> fac(modsize);
vector<ll> inv(modsize);
vector<ll> facinv(modsize);

void modcalc() {
	if (modsize == 0) abort();
	fac[0] = 1; fac[1] = 1; inv[1] = 1;
	facinv[0] = 1; facinv[1] = 1;
	for (ll i = 2; i < modsize; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		facinv[i] = facinv[i - 1] * inv[i] % mod;
	}
}

ll modinv(ll a) {
	if (a == 0) abort();
	ll b = mod, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= mod;
	if (u < 0) u += mod;
	return u;
}

ll modpow(ll a, ll b) {
	ll ans = 1;
	a %= mod;
	while (b) {
		if (b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

ll modcomb(ll n, ll k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * facinv[k] % mod * facinv[n - k] % mod;
}

ll modperm(ll n, ll k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * facinv[n - k] % mod;
}

ll modhom(ll n, ll k) {
	if (n < 0 || k < 0 || n == 0 && k > 0) return 0;
	if (n == 0 && k == 0) return 1;
	return fac[n + k - 1] * facinv[k] % mod * facinv[n - 1] % mod;
}

ll dp[5010][5010];

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

	ll n, m;
	cin >> n >> m;
	rep(j, m + 1) dp[1][j] = modpow(2, j);
	rep(i, n + 1) {
		ll p = 0;
		rep(j, m + 1) {
			dp[i + 1][j] += dp[i][j] * (j + 1) % mod;
			if (j >= 2) {
				p *= 2;
				p += (j - 1) * dp[i][j - 1] % mod;
				p %= mod;
			}
			dp[i + 1][j] += p;
			dp[i + 1][j] %= mod;
		}
	}
	cout << dp[n][m] << '\n';
}

Measured memory_bytes: 199336
#include <bits/stdc++.h>
//#include "atcoder/all"
typedef long long int ll;
using namespace std;
// using namespace atcoder;
int main() {
    string s;
    cin >> s;
    if (s[s.length() - 1] == 's') {
        cout << s << "es" << endl;
    }
    else {
        cout << s << "s" << endl;
    }
    return 0;
}

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

int main()
{
    int n,i;
    bool pass = false;
    vector<bool> v;
    cin>>n;
    for(i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a==b)
            v.push_back(true);
        else
            v.push_back(false);
    }
    for(i=1;i<n-1;i++)
    {
        if(v[i-1] && v[i] && v[i+1])
            pass = true;
    }
    if(pass)
        cout<<"Yes";
    else
        cout<<"No";
}



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

int main() {
    int k;
    string s;
    cin >> k >> s;
    
    if(s.size() <= k)
        cout << s << endl;
    else {
        rep(i,k) {
            cout << s[i];
        }
        cout << "..." << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

int extgcd(int a, int b, int &x, int &y){
	int d = a;
	if(b != 0){
		d = extgcd(b, a%b, y , x);
		y -= (a/b) * x;
	}
	else {
		x = 1, y = 0;
	}
	return d;
}

int main(){
	int a, b, x, y;
	cin >> a >> b;
	int c = extgcd(a,b,x,y);
	cout << x << " " << y << endl;
	return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#define ll signed long long int
#define MAXX 10005
#define FAST ios_base:sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;


signed main()
{
	ll a, b, c;
	cin >> a >> b >> c;
	cout << c << " " << a << " " << b;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		//		new Main().solveA();
		//		new Main().solveB();
		//		new Main().solveC();
		//		new Main().solveC2();
		new Main().solveC3();
		// new Main().solveD();
	}

	private void solveA() {
		Scanner scanner = null;
		String line = "";

		try {
			scanner = new Scanner(System.in);
			line = scanner.next();

			System.out.println(line.replaceAll("2017", "2018"));

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveB() {
		Scanner scanner = null;
		int n = 0;

		try {
			scanner = new Scanner(System.in);
			n = scanner.nextInt();
			int[] wk = new int[n];

			for (int i = 0; i < n; i++) {
				wk[i] = scanner.nextInt();
			}

			Arrays.sort(wk);

			int res = 0;
			for (int i = 0; i < wk.length; i++) {
				if (i == 0) {
					res++;
				} else if (wk[i] != wk[i - 1]) {
					res++;
				}

			}

			System.out.println(res);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveC2() {
		Scanner scanner = null;
		int n = 0;
		int y = 0;

		try {
			scanner = new Scanner(System.in);
			n = scanner.nextInt();
			y = scanner.nextInt();

			for (int i = n; i >= 0; i--) {
				if (i * 10000 > y) {
					continue;
				}
				for (int j = 0; j <= n - i; j++) {
					int k = n - i - j;
					if (i * 10000 + j * 5000 + k * 1000 == y) {
						System.out.println(i + " " + j + " " + k);
						return;
					}
				}
			}

			System.out.println(-1 + " " + -1 + " " + -1);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveC3() {
		Scanner scanner = null;
		int n = 0;
		int y = 0;

		try {
			scanner = new Scanner(System.in);
			n = scanner.nextInt();
			y = scanner.nextInt();

			for (int i = n; i >= 0; i--) {
				if (i * 10000 > y) {
					continue;
				}
				for (int j = 0; j <= n; j++) {
					if (i * 10000 + j * 5000 + (n - i - j) * 1000 == y && i + j <= n) {
						System.out.println(i + " " + j + " " + (n - i - j));
						return;
					}
				}
			}

			System.out.println(-1 + " " + -1 + " " + -1);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveC() {
		Scanner scanner = null;
		int n = 0;
		int y = 0;

		try {
			scanner = new Scanner(System.in);
			n = scanner.nextInt();
			y = scanner.nextInt();

			for (int i = n; i >= 0; i--) {
				if (i * 10000 > y) {
					continue;
				}
				for (int j = 0; j <= n - i; j++) {
					for (int k = 0; k <= n - i - j; k++) {
						if (n == i + j + k && i * 10000 + j * 5000 + k * 1000 == y) {
							System.out.println(i + " " + j + " " + k);
							return;
						}
					}
				}
			}

			System.out.println(-1 + " " + -1 + " " + -1);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveD() {
		Scanner scanner = null;
		int lineAB = 0;
		int lineBC = 0;
		int lineCA = 0;

		try {
			scanner = new Scanner(System.in);
			lineAB = scanner.nextInt();

			System.out.println("");

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}
}

Measured memory_bytes: 21204
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	static final PrintStream out = System.out;
	static Scanner sc = new Scanner(System.in);
	static final long Mod = 1000_000_007L;
	public static void main(String[] args) {
		Main main = new Main();
		main.solve();
		System.exit(0);
	}

	void solve() {
		long A = nextInt();
		long B = nextInt();
		long K = (A+B)/2;

		if(Math.abs(A-K) == Math.abs(B-K)) {
			out.println(K);
		}else{
			out.println("IMPOSSIBLE");
		}
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)a[i] = nextInt();
		return a;
	}
	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)a[i] = nextLong();
		return a;
	}
	public int nextInt() {
		return Integer.parseInt(next());
	}
	public long nextLong() {
		return Long.parseLong(next());
	}
	public String next() {
		return sc.next();
	}

}

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

int main(){
	
	int n;cin>>n;
	if(n%1000==0){
		cout<<"0";
	}else{
		int i=1;
		while(1){
			if(n<1000*i){
				cout<<1000*i-n;
				break;
			}
			i++;
		}
	}
	return 0;
}

Measured memory_bytes: 3636
#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define INF 1e9
using ll = std::int64_t;

template <class T>bool chmax(T &a, const T &b);
template <class T>bool chmin(T &a, const T &b);
//最大公約数
std::int64_t gcd(std::int64_t a, std::int64_t b);
std::int64_t gcd_s(std::int64_t aa, std::int64_t bb);
//ラングレス圧縮
std::vector<std::pair<char, std::int64_t>> rle(std::string str);
//素数判定
bool is_prime(std::int64_t n);
// 約数の列挙
std::vector<std::int64_t> divisor(std::int64_t n);
// 素因数分解
std::map<std::int64_t,std::int64_t> prime_factor(std::int64_t n);

//10^9 + 7
#define yojo 1000000007
#define MAX_NUM 200001

void Main()
{
  string s;
  cin >> s;
  sort(all(s));
  
  for (int i = 0; i < s.size() - 1; i++)
  {
    if (s[i] == s[i + 1])
    {
      std::cout << "no" << std::endl;
      return;
    }
  }
  
  std::cout << "yes" << std::endl;

  return;
}

int main()
{
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}

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

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

//最大公約数
std::int64_t gcd(std::int64_t a, std::int64_t b)
{
  // a >= b && b != 0
  std::int64_t c;
  do
  {
    c = a % b;
    a = b;
    b = c;
  } while (c);

  return a;
}

//最大公約数安全版
std::int64_t gcd_s(std::int64_t aa, std::int64_t bb)
{
  std::int64_t a = max(aa, bb);
  std::int64_t b = min(aa, bb);
  std::int64_t c;
  if (b == 0)
  {
    return -1;
  }
  do
  {
    c = a % b;
    a = b;
    b = c;
  } while (c);

  return a;
}

//ラングレス圧縮
std::vector<std::pair<char, std::int64_t>> rle(std::string str)
{
  std::vector<std::pair<char, std::int64_t>> data;
  char now = str[0];
  std::int64_t count = 0;
  for (std::int64_t i = 0; i < str.size() + 1; i++)
  {
    if (i == str.size())
    {
      data.push_back(make_pair(str[i - 1], count));
      break;
    }
    else if (now != str[i])
    {
      data.push_back(make_pair(now, count));
      now = str[i];
      count = 0;
    }
    count++;
  }

  return data;
}

//素数判定
bool is_prime(std::int64_t n)
{
  for (std::int64_t i = 0; i * i <= n; i++)
  {
    if (n % i == 0)
    {
      return false;
    }
  }
  
  return n != 1;
}

//約数の列挙
std::vector<std::int64_t> divisor(std::int64_t n)
{
  std::vector<std::int64_t> res;
  for (int i = 0; i < n; i++)
  {
    if(n % i == 0){
      res.push_back(i);
      if (i != n / i) res.push_back(n / i);
    }
  }
  return res;
}

// 素因数分解
std::map<std::int64_t, std::int64_t> prime_factor(std::int64_t n)
{
  std::map<std::int64_t, std::int64_t> res;
  for (int i = 2; i * i <= n; i++)
  {
    while (n % i == 0)
    {
      ++res[i];
      n /= i;
    }
  }

  if (n != 1)
  {
    res[n] = 1;
  }
  
  return res;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repe(i,n) for (int i = 0; i <= (n); ++i)
#define repe1(i,n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define eb(k,v) emplace_back(k,v)
#define ct(res) cout << res << "\n";
#define vi vector<int>
#define vl vector<ll>
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    int ans = 0;
    int tmp = 0;
    rep(i,s.size()) {
        if (s[i]=='A'||s[i]=='T'||s[i]=='C'||s[i]=='G') {
            tmp++;
        } else {
            tmp = 0;
        }
        ans = max(ans,tmp);
    }
    cout << ans << "\n";
}



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

int main() {
  
  int N;
  int A;
  
  cin >> N >> A;
  
  if ( N % 500 <= A ) {
    
    cout << "Yes" << endl;
  }
  
  else {

    cout << "No" << endl;
  }
}

Measured memory_bytes: 3536
#include <bits/stdc++.h>
#define INF 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int x[101];

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&x[i]);
	}
	int ans=INF;
	for(int i=0;i<=100;i++){
		int cur=0;
		for(int j=0;j<n;j++){
			cur+=(i-x[j])*(i-x[j]);
		}
		ans=min(cur,ans);
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int
main()
{
    int n_lines;

    cin >> n_lines;
    cin.ignore();

    while (n_lines--) {
        string text;
        int cursor = 0;
        int n_commands;

        getline(cin, text);
        cin >> n_commands;
        cin.ignore();

        while (n_commands--) {
            string command;
            getline(cin, command);

            if (command == "forward char") {
                if (cursor < text.size()) cursor++;
            } else if (command == "forward word") {
                while (cursor < text.size() && text[cursor] == ' ') cursor++;
                while (cursor < text.size() && text[cursor] != ' ') cursor++;
            } else if (command == "backward char") {
                if (cursor > 0) cursor--;
            } else if (command == "backward word") {
                while (cursor > 0 && text[cursor - 1] == ' ') cursor--;
                while (cursor > 0 && text[cursor - 1] != ' ') cursor--;
            } else if (command.find("insert ") == 0) {
                size_t start = command.find_first_of('"') + 1;
                size_t end = command.find_first_of('"', start);
                string arg = command.substr(start, end - start);

                text = text.substr(0, cursor) + arg + text.substr(cursor);
                cursor += arg.size();
            } else if (command == "delete char") {
                if (cursor < text.size()) {
                    text.erase(cursor, 1);
                }
            } else if (command == "delete word") {
                if (cursor < text.size()) {
                    size_t word_end = cursor;

                    while (word_end < text.size() && text[word_end] == ' ')
                        word_end++;
                    if (word_end == text.size()) continue;

                    while (word_end < text.size() && text[word_end] != ' ')
                        word_end++;

                    text = text.substr(0, cursor) + text.substr(word_end);
                }
            }
        }

        cout << text.substr(0, cursor) << '^' << text.substr(cursor) << endl;
    }
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD=1e9+7;
ll inv(ll);
ll power(ll x, ll n){
    if (n==0) return 1;
    if (n<0) return power(inv(x), -n);
    auto pow_harf = power(x, n/2);
    if (n%2==0) return (pow_harf * pow_harf) % MOD;
    return ((pow_harf * pow_harf) % MOD * x) % MOD;
}
ll inv(ll x){
    // フェルマーの小定理から x^(p-2) == x^(-1) (mod p)
    return power(x, MOD - 2);
}
auto fact(ll x){
    // 再帰だとスタックオーバーフローするので
    ll ret = 1;
    for(ll a=2; a<=x; ++a){
        ret = (ret * a) % MOD;
    }
    return ret;
}
/*
【解法】
A = [1, 2, ..., n] と固定する（求める場合の数は、固定した場合の数の mPn 倍）。B を長さ n の数列とする

ある集合 S \subset {1, ..., n} の上で値が一致する（そのほかにも一致する値のある可能性がある）ような B の場合の数は g(S) = (m-|S|)P(n-|S|) 通り
（まだ決まっていない n-|S| 箇所の値を、使っていない m-|S| 個の値から重複しないように決める）

ある集合 S \subset {1, ..., n} の上でちょうど値が一致する（ S に属さない点 i ではA[i] != B[i] となる）ような
B の場合の数を f(S) 通りとすると、g(S) = \sum_{S\subset T} f(T) となる。

F(S) = f({1, ..., n} \setminus S), G(S) = g({1, ..., n} \setminus S) とおくと、
G(S) = \sum_{T\subset S} F(S) なので、包除原理から F(S) = \sum_{T\subset S} (-1)^|S\setminus T| G(T) が成り立つ。

求めるのは f(\emptyset)
= F({1, ..., n})
= \sum_{T\subset {1, ..., n}} (-1)^|{1, ..., n}\setminus T| G(T)
= \sum_{T\subset {1, ..., n}} (-1)^|{1, ..., n}\setminus T| g({1, ..., n} \setminus T)
= \sum_{T\subset {1, ..., n}} (-1)^|T| g(T)
（ T -> T\setminus {1, ..., n} で置換）
ここで g は size の関数なので g(T) = g(|T|) とおくと、 k 元集合の選び方が nCk 通りなので 
= \sum_{k=0}^n (-1)^k nCk g(k)
= \sum_{k=0}^n (-1)^k n! / (n-k)! / k! * (m-k)! / (m-n)!
となる。

これを高速に計算する。 k == 0 のとき m! / (m-n)! で、

    n! (m-k)!             n! (m-(k-1))!          n-k+1
---------------- == ------------------------ * ---------
(n-k)! k! (m-n)!    (n-(k-1))! (k-1)! (m-n)!   (m-k+1) k

なので、 k がふえるたびに (n-k+1) / (m-k+1) / k 倍すればよい
*/
int main()
{
    ll n, m;
    cin >> n >> m;

    const ll mpn = fact(m) * inv(fact(m-n)) % MOD;
    ll tmp = mpn;
    ll sum = tmp;
    for(int k=1; k<=n; ++k){
        tmp = ((tmp * inv(m-k+1)) % MOD * inv(k) % MOD) * (n-k+1) % MOD;
        ll sign = (k%2==0) ? 1 : (MOD - 1);
        sum = (sum + sign * tmp) % MOD;
    }
    cout << (sum * mpn) % MOD;
    return 0;
}


Measured memory_bytes: 3580
from collections import Counter,defaultdict,deque
from heapq import heapify,heappop,heappush
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
res = 0
if k == 0:
    res = n**2
else:
    for i in range(k+1,n+1):
        res += (i - k)*((n+1) // i)
        t = n % i
        if t == i-1:
            continue
        if t >= k:
            res += t-k+1
print(res)

    


Measured memory_bytes: 39532
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

#include <cstdio>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define swap(a, b, type) { type _tmp = a; a = b; b = _tmp; }
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int N;
	int ans;

	cin >> N;

	if (N % 2 == 0) ans = N / 2 - 1;
	else ans = N / 2;

	cout << ans << endl;

	return 0;
}


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

int main() {
  long long n,a=2,b=1;
  cin>>n;
  for(int i=2;i<=n;i++){
    if(i%2==0)
      a+=b;
    else
      b+=a;
  }
  if(n%2==0)
    cout<<a<<endl;
  else
    cout<<b<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main ()
{
int a , b ;
  scanf("%d\n",&a);
  scanf("%d\n",&b);
  if ( (a * b * 3) % 2 != 0 || (a * b * 1) % 2 != 0 )
  {
    printf("Yes");
  }
  else{
printf("No");
  }
  return 0 ;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
int main() {
    int N, M;
    cin >> N >> M;
    vector<P> v(M);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        v[i] = P(b, a);
    }
    sort(v.begin(), v.end());
    int cnt = 1;
    int point = v[0].first;
    for (int i = 1; i < M; i++) {
        if (point <= v[i].second) {
            cnt++;
            point = v[i].first;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
using namespace std;
#define int long long int 
#define double long double
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> new_data_set;
const int inf=1e18;
bool isprime(int n)
	{
    	if(n==1) return true;
    	for(int i = 2;i*i<=n;i++){
    		if(n%i==0) return false;
		}
		return true;
	}
int lcm(int a,int b){
	return (a*b)/__gcd(a,b);
}
int gcd(int a, int b) 
{ 
    if (b == 0){
    	return a;
	} 
    return gcd(b, a % b);  
      
} 
unsigned int factorial(unsigned int n) 
{ 
    if (n == 0) 
    return 1; 
    return n * factorial(n - 1); 
} 
//int dsu[1000001],s[100005];
void init(int n,int m){
	for(int i=1;i<=n;i++){
		//dsu[i]=i;
		//s[i]=1;
	}
}
//int root(int x){
//	while(dsu[x]!=x){
//		x = dsu[x];
//	}
//	return x;
//}
//void uni(int x,int y){
//	int p = root(x);
//	int q = root(y);
//	if(p==q){
//		return;
//	}
//	else{
//		if(s[p]<s[q]){
//			s[q]+=s[p];
//			dsu[p] = q;
//		}
//		else{
//			s[p]+=s[q];
//			dsu[q] = p;
//		}
//	}
//}
int power(int x, unsigned int y)  
{  
    int res = 1;
    x = x ; 
    if (x == 0) return 0;  
    while (y > 0){  
        if (y & 1){
        	res*=x;
        	//res%=p;
		}   
        y = y>>1;  
        x = (x*x); 
		//x%=p;
		//res%=p; 
    }  
    return res;  
}
vector<int>graph[200001],road[100001];
vector<int>rgraph[100001];
int modInverse(int n, int p){
    return power(n, p-2);
}
 
// Returns nCr % p using Fermat's little theorem.
int nCrmodp(int n, int r, int p){
   // Base case
   if (r==0)
      return 1;
    else if(n<r)
        return 0;
    else{
        // Fill factorial array so that we can find all factorial of r, n and n-r
        int fac[n+1];
        fac[0] = 1;
        for (int i=1 ; i<=n; i++)
            fac[i] = (fac[i-1]*i)%p;
 
        return (fac[n]* modInverse(fac[r], p) % p * modInverse(fac[n-r], p) % p) % p;
    }
}
bool sorted(int n,int arr[]){
	int b[n];
	for(int i=0;i<n;i++){
		b[i]=arr[i];
	}
	sort(b,b+n);
	for(int i=0;i<n;i++){
		if(b[i]!=arr[i]){
			return false;
		}
	}
	return true;
}
struct node{
	int x,y;
};
deque<int>dq;
vector<vector<vector<int>>>dp(3001,vector<vector<int>>(3001,vector<int>(4)));
int arr[3001][3001];
signed main(){
	FAST
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=0;i<k;i++){
		int x,y,z;
		cin>>x>>y>>z;
		arr[x][y]=z;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j][0]=*max_element(dp[i-1][j].begin(),dp[i-1][j].end());
			dp[i][j][1]=dp[i][j][0]+arr[i][j];
			for(int k=1;k<4;k++){
				dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k]);
				dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+arr[i][j]);
			}
		}
	}
	cout<<*max_element(dp[n][m].begin(),dp[n][m].end());
}

 
 
 

Measured memory_bytes: 716508