akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 2*1e5;

int n, k, a[N], dp[N];

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

    cin >> n >> k;

    for (int i = 0; i < n; ++ i)
        cin >> a[i];

    for (int i = 1; i < n; ++ i) {
        dp[i] = 100000*N;
        for (int j = 1; j <= k and i-j >= 0; ++ j)
            dp[i] = min(dp[i], dp[i-j]+abs(a[i]-a[i-j]));
    }

    cout << dp[n-1] << endl;

    return 0;
}


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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int sum;
		while(true) {
			String line = br.readLine();
			if("0".equals(line)) {
				break;
			}
			char[] c = line.toCharArray();
			sum = 0;
			for(int i = 0; i < c.length; ++i) {
				sum += Character.getNumericValue(c[i]);
			}
			sb.append(sum).append("\n");
		}
		System.out.print(sb);
	}
}

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

// utility of stdin,stdout
#define INPS cin >>
#define BUFS cout << 
#define BUFE << endl 

int main(int argc, char const *argv[]){
	int i,win = 0,lose = 0;
	string s;
	cin >> s;
	for (i = 0; i < s.size(); ++i)
	{
		if(s.at(i) == 'o')	++win;
		else ++lose;
	}
	if(win + (15 - i) >= 8)	BUFS("YES") BUFE;
	else BUFS("NO") BUFE;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int dis[50][2], chk[50][2], dst[50], n, m, mindst;
int min(int a, int b){
	return a < b ? a : b;
}

int dist(int aluno){
	int x1 = dis[aluno][0], y1 = dis[aluno][1];
	mindst = 2147483647;
	for(int i = 0; i < m; ++i){
		int x2 = chk[i][0], y2 = chk[i][1];
		dst[i] = abs(x1 - x2) + abs(y1 - y2);
		mindst = min(mindst, dst[i]);
	}
	for(int i = 0; i < m; ++i){
		if(dst[i] == mindst) return i;
	}
	return m-1;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; ++i){
		scanf("%d%d", &dis[i][0], &dis[i][1]);
	}
	for(int i = 0; i < m; ++i){
		scanf("%d%d", &chk[i][0], &chk[i][1]);
	}
	for(int i = 0; i < n; ++i){
		printf("%d\n", dist(i)+1);
	}
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>
int main(void){
    int n,l,min=1000000,t,i,sum=0,a;
    scanf("%d %d",&n,&l);
    for(i=0;i<n;i++){
        t=l+i;
        sum+=t;
        if(abs(t)<min){
            min=abs(t);
            a=t;
        }
    }
    printf("%d",sum-a);
    return 0;
}


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

namespace ARC68_C
{
    class Program
    {
        static void Main(string[] args)
        {

            var x = long.Parse(Console.ReadLine());

            long m = 0;
            if (x % 11 > 0 && x % 11 < 7) m = 1;
            if (x % 11 > 6) m = 2;
            Console.WriteLine( 2 * (x / 11) + m);
        }
    }
}


Measured memory_bytes: 11092
def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=True)
    def helper(x):
        p = len(A) - 1
        t = 0
        for a in A:
            while p >= 0 and A[p] + a < x:
                p -= 1
            t += p + 1
        return t
    l, r = 0, A[0] * 2 + 1
    while r - l > 1:
        m = (l + r) // 2
        if helper(m) > M:
            l = m
        else:
            r = m
    k = sum(A)
    p = len(A) - 1
    t = (M - helper(l)) * l
    for a in A:
        while p >= 0 and A[p] + a < l:
            k -= A[p]
            p -= 1
        t += a * (p + 1) + k
    print(t)

main()


Measured memory_bytes: 14268
#include <iostream>
using namespace std;
int main(void){

	int n, m;

	cin >> n >> m;

	char date[64][64];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> date[i][j];
		}
	}
	int count, ans = 999999;

	for (int WB = 1; WB < n - 1; WB++) {
		for (int BR = 1; WB + BR < n; BR++) {
			
			count = 0;
			int row = 0;
			for (int i = 0; i < WB; i++) {
				for (int i2 = 0; i2 < m; i2++) {
					if (date[row][i2] != 'W') { count++; }
				}
				row++;
			}

			for (int i = 0; i < BR; i++) {
				for (int i2 = 0; i2 < m; i2++) {
					if (date[row][i2] != 'B') { count++; }
				}
				row++;
			}

			for (int i = 0; i + WB + BR < n; i++) {
				for (int i2 = 0; i2 < m; i2++) {
					if (date[row][i2] != 'R') { count++; }
				}
				row++;
			}
			if (ans > count) { ans = count; }
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3040
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))
kionsa_min = float("INF")
for i in range(n):
    kionsa = abs(a - (t - h[i] * 0.006))
    if kionsa < kionsa_min:
        ans = i
        kionsa_min = kionsa
print(ans + 1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(n) ((int)(n).size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

int dp[3010][3010];
string s,t;

int solve(int i, int j){
  if(i >= SZ(s) || j >= SZ(t)) return 0;
  int &r = dp[i][j];
  if(r >= 0) return r;
  r = max(solve(i+1,j), solve(i,j+1));
  if(s[i] == t[j]) r = max(r, 1+solve(i+1,j+1));
  return r;
}

int main(){FIN;
  memset(dp,-1,sizeof(dp));
  cin >> s >> t;
  int i = 0, j = 0;
  string ans = "";
  while(i < SZ(s) && j < SZ(t)){
    if(s[i] == t[j] && solve(i,j) == 1+solve(i+1,j+1)) ans += s[i], i++,j++;
    else if(solve(i,j) == solve(i+1,j)) i++;
    else j++;
  }
  cout << ans << "\n";
}

Measured memory_bytes: 36224
def resolve():
    h, w = map(int, input().split())
    c = list(list(map(int, input().split())) for _ in range(10))
    a = list(list(map(int, input().split())) for _ in range(h))
    for k in range(10):  # 経由
        for i in range(10):  # 始点
            for j in range(10):  # 終点
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
    costs = [c[i][1] for i in range(10)]
    costs += [0]  # -1の分
    ans = 0
    for i in range(h):
        for j in range(w):
            ans += costs[a[i][j]]
    print(ans)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3444
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    int n;

    scanf("%d", &n);

    double x1, y1, x2, y2, x3, y3;

    while (n--) {
        scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
 
        if (y1 == y3) {
            swap(x3, x2);
            swap(y3, y2);
        }

        if (y2 == y3) {
            swap(x3, x1);
            swap(y3, y1);
        }

        double a = x2 - x3;
        double b = y2 - y3;
        double c = x2 + x3;
        double d = y2 + y3;
        double e = x3 - x1;
        double f = y3 - y1;
        double g = x3 + x1;
        double h = y3 + y1;

        double px = ((a / b) * (c / 2) + d / 2 - (e / f) * (g / 2) - h / 2) / (a / b - e / f);
        double py = -(a / b) * px + (a / b) * c / 2 + d / 2;
        double x = x1 - px;
        double y = y1 - py;
        double r = sqrt(x * x + y * y);

        printf("%.3lf %.3lf %.3lf\n", px, py, r);
    }

    return 0;
}

Measured memory_bytes: 2592
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
//if(strcmp(s[i],"AC")==0)
//if(s[l]=='#')
/*小文字判定
if((moji>= 'a') && (moji<='z')){
    printf("a\n");
    return 0;
  }
  */

int W_Length(char *str){
	int length = 0;
	while(*str++ != '\0')
		length++;
	return length;
}

void swap(long long int *a, long long int *b){
  int temp;
  temp=*a;
  *a=*b;
  *b=temp;
}
//swap(&a, &b)

double deg(double theta){//deg to theta
return theta*(2*3.14159265359)/360;
}

long long int cmp( const void *p, const void *q ) {
    return *(long long int*)p - *(long long int*)q;
}//ちいさい順
//qsort(a,n,sizeof(long long int),cmp);


int cmp_s(const void * left, const void * right)
{
	char *left_char = (char *)left;
  char *right_char = (char *)right;
  return strcmp(left_char, right_char);
}
//qsort(s,n,sizeof(s[0]),cmp_s);
//char s[n][11]

long long int GCD(long long int a, long long int b){
  long long int L=a,S=b;
  while(1){
    if(S>L){
      L=S+L;
      S=L-S;
      L=L-S;
    }
    if(L%S==0){
      return S;
    }
    L=L%S;
  }
  
}

long long int LCM(long long int a, long long int b){
  return a*b/(GCD(a,b));
}

int main (void)
{
	long long int p[5005],b,c,n,i,min,k,a[210000],max,j=1,t[210000],count=0;
scanf("%lld",&n);
for(i=0;i<n;i++){
  scanf("%lld",&a[i]);
}  
  min=a[0];
  for(i=0;i<n;i++){
    if(a[i]<=min){
      min=a[i];
      count++;
    }
  }
  
  printf("%lld",count);
return 0;
}


Measured memory_bytes: 3296
#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;

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

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

  int n, m;
  cin >> n >> m;
  vector<unordered_set<int> > edge;
  for (int i = 0; i < n; i++) edge.push_back(unordered_set<int>());
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    edge[a-1].insert(b-1); // zero index
  }
  int s, t;
  cin >> s >> t;
  s--; t--; // zero index

  queue<Pii> q;
  q.push(Pii(s, 0));
  const int unreachable = 1000000007;
  vector<int> minimum(n, unreachable);
  vector<int> current(n, 0);
  while (!q.empty()) {
    Pii now = q.front();
    q.pop();
    if (now.second % 3 == 0) {
      if (now.second < minimum[now.first]) minimum[now.first] = now.second;
      else continue;
    }
    for (int i : edge[now.first]) {
      if (now.second+1 != current[i]) {
        q.push(Pii(i, now.second+1));
        current[i] = now.second+1;
      }
    }
  }

  if (minimum[t] == unreachable) cout << -1 << endl;
  else cout << minimum[t]/3 << endl;
  return 0;
}


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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	char a, b;
	cin >> a >> b;
	if(a == 'H') cout << b << endl;
	else{
		if(b == 'H') cout << 'D' << endl;
		else cout << 'H' << endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
const int MAX_NM = 200;

struct M{
	int r, h;
};

bool ascending_M_r(const M& l, const M& r){
	return l.r < r.r;
}

bool ascending_M_h(const M& l, const M& r){
	return l.h < r.h;
}

int main(){
	int n, m, dp[MAX_NM];
	M a[MAX_NM];
	while(std::cin >> n, n){
		for(int i=0;i<n;i++){
			std::cin >> a[i].h >> a[i].r;
		}
		std::cin >> m;
		for(int i=0;i<m;i++){
			std::cin >> a[n+i].h >> a[n+i].r;
		}
	
		int r_res = 0, h_res = 0;//hの最長増加部分列とrの最長増加部分列
		std::sort(a, a+n+m, ascending_M_r);

		dp[0] = 1;
		for(int i=1;i<n+m;i++){
			dp[i] = 1;
			for(int j=0;j<i;j++){
				if(a[j].r < a[i].r && a[j].h < a[i].h){
					dp[i] = std::max(dp[i], dp[j]+1);
				}
			}
		}
		r_res = dp[n+m-1];

		std::sort(a, a+n+m, ascending_M_h);
		dp[0] = 1;
		for(int i=1;i<n+m;i++){
			dp[i] = 1;
			for(int j=0;j<i;j++){
				if(a[j].r < a[i].r && a[j].h < a[i].h){
					dp[i] = std::max(dp[i], dp[j]+1);
				}
			}
		}
		h_res = dp[n+m-1];

		printf("%d\n", std::max(h_res, r_res));
	}
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define int long long
//#define ll long long
#define pb push_back
#define x first
#define ld long double
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) a.begin(),a.end()

using namespace std;

using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <ld> a(n);
    for (auto &i : a) cin >> i;
    sort(all(a));
    ld last = a[0];
    for (int i = 1; i < n; i++) {
        last = (last + a[i]) / 2.0;
    }
    cout << fixed;
    cout.precision(10);
    cout << last << '\n';
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<functional>
#include<cmath>
#include<algorithm>
typedef long long ll;

int main() {
	std::string str;
	char c;
	int found[26] = { false };
	std::cin >> str;
	for (int i = 0; i < str.size(); i++) {
		found[str[i]-'a'] = true;
	}
	for (int i = 0; i < 26; i++) {
		if (found[i] == false) {
			c = 'a' + i;
			std::cout << c << std::endl;
			return 0;
		}
	}
	std::cout << "None" << std::endl;
}

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

from collections import Counter
# N = int(input())
# S = input()
N, K = map(int, input().split())
A = list(map(int, input().split()))

def main():
    cnt_a = Counter(A).most_common()[::-1]
    task = len(cnt_a) - K
    if task <= 0:
        print(0)
        exit()
    ans = 0
    for i, v in enumerate(cnt_a, 1):
        ans += v[1]
        if i == task:
            print(ans)
            exit()

if __name__ == "__main__":
    main()



Measured memory_bytes: 39320
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

void prime_factorization(ll N, map<ll, int>& res) {
  if(N == 1 || N == 0) return;
  ll n = N;
  ll i = 2;
  while(n >= i * i) {
    while(n % i == 0) {
      if(res.count(i)) res[i]++;
      else res[i] = 1;
      n /= i;
    }
    if(i == 2) i++;
    else i += 2;
  }
  if(n != 1) res[n]++;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n; cin >> n;
  map<ll, int> primes;
  prime_factorization(n, primes);
  int ans = 0;
  for(auto ele: primes) {
    for(int i=1; i<=100; i++) {
      if(ele.second < i*(i+1)/2) {
        ans += (i-1);
        break;
      }
    }
  }
  cout << ans << endk;
  return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  string s;
  cin>>s;
  string x(7,'.');
  for(int i=0;i<4;i++) x[i*2]=s[i];
  int a=s[0]-'0',b=s[1]-'0',c=s[2]-'0',d=s[3]-'0';
  if(a+b+c+d==7){
    x[1]='+';x[3]='+';x[5]='+';
  }
  if(a+b+c-d==7){
    x[1]='+';x[3]='+';x[5]='-';
  }
  if(a+b-c+d==7){
    x[1]='+';x[3]='-';x[5]='+';
  }
  if(a+b-c-d==7){
    x[1]='+';x[3]='-';x[5]='-';
  }
  if(a-b+c+d==7){
    x[1]='-';x[3]='+';x[5]='+';
  }
  if(a-b+c-d==7){
    x[1]='-';x[3]='+';x[5]='-';
  }
  if(a-b-c+d==7){
    x[1]='-';x[3]='-';x[5]='+';
  }
  if(a-b-c-d==7){
    x[1]='-';x[3]='-';x[5]='-';
  }
  cout<<x<<"=7"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

struct Solver {
	void solve() {
		string s;
		cin >> s;

		int n = (int)s.size();
		if( n == 26 ) {
			for( int i = n-1; i >= 0; --i ) {
				char ch = s[i];
				while( ++ch <= 'z' ) {
					if( s.find( ch ) >= (size_t)i ) {
						break;
					}
				}

				if( ch <= 'z' ) {
					cout << s.substr( 0, i ) << ch << endl;
					return;
				}
			}
		}
		else {
			for( char i = 'a'; i <= 'z'; ++i ) {
				if( s.find(i) >= (size_t)n ) {
					cout << s << i << endl;
					return;
				}
			}
		}

		cout << -1 << endl;
	}
};

int main() {
	ios::sync_with_stdio( false );
	cout << fixed << setprecision( 10 );
	Solver().solve();
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n,h,m=0,ans=0,a[111111],b[111111];
int main(){
	scanf("%d%d",&n,&h);
	for (int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
		m=max(m,a[i]);
	}
	sort(b+1,b+n+1);
	for (int i=n;i&&b[i]>m&&h>0;i--){
		h-=b[i];
		ans++;
	}
	if (h>0){
	   ans+=(h+m-1)/m;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 1024
a,b,c = map(int,input().split())
if a==b==c:
    if a%2==0:
        print(-1)
        exit()
    else:
        print(0)
        exit()
cnt = 0
while not (a%2+b%2+c%2):
    cnt+=1
    a,b,c = b//2+c//2,a//2+c//2,a//2+b//2
print(cnt)

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

void Trim(deque<bool>& whites)
{
	while (!whites.empty() && !whites.front())
		whites.pop_front();
	while (!whites.empty() && whites.back())
		whites.pop_back();
}

int main()
{
	auto& in = cin;

	int N;
	in >> N;
	deque<bool> whites(N);
	int num = 0;
	for (int i = 0; i < N; ++i) {
		char c;
		in >> c;
		if (c == 'W') {
			whites[i] = true;
			++num;
		}
	}
	if (num == (int)whites.size() || num == 0) {
		cout << 0;
		return 0;
	}

	num = 0;
	for (;;) {
		Trim(whites);
		if (whites.empty())
			break;
		whites.front() = false;
		whites.back() = true;
		++num;
	}

	cout << num;

	return 0;
}


Measured memory_bytes: 3792
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

template<class T> ostream& operator<<(ostream &os, vector<T> V) {
 os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
	return os << "(" << P.first << "," << P.second << ")";}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif


#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define I insert 
#define pb push_back
#define F first
#define S second
#define endl "\n"

int mod=1e9+7;
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline int inv(int a){return power(a,mod-2);}
inline void modadd(int &a,int &b){a+=b;if(a>=mod)a-=mod;} 


int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
	ll n;ll i,j;
	cin>>n;
	if(n==1){
		cout<<n;
	}
	else if(n==2){
		cout<<n*n;
	}
	else {
		vll v(n+1,0);
		ll ans = 0 ;
		v[0] = 1;v[1]=1;v[2] = 1;
		ll tot = 3;
		for(i=3;i<=n;i++){
			v[i] = sub(tot,v[i-2]);tot = add(tot,v[i]);
		}
		for(i=1;i<=n-1;i++){
			ll x = mul(v[i-1],mul(n-1,n-1));
			ans = add(ans,x);
			x = mul(v[i-1],i);
			ans = add(ans,x);
		}
		ans = add(ans,v[n]);
		ans = add(ans,mul(v[n-1],n-1));
		cout<<ans;
	}
	
}


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

using namespace std;

int main(){
	string s;
	cin >> s;
	int a, z;
	bool j = false;
	for(int i=0; i<s.length(); i++){
		if(s[i] == 'A' && j == false){
			a = i;
			j = true;
		}
		if(s[i] == 'Z') z = i;
	} 
	cout << z-a+1 << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int main(){
	string S, T;
	cin >> S >> T;
	if(S.size() < 1 || S.size() > 10){
		cout << "No";
		return 0;
	}
	if(!strncmp(S.c_str(), T.c_str(), S.size()) && T.size() == S.size()+1){
		cout << "Yes";
	} else {
		cout << "No";
	}
	return 0;
	
}

Measured memory_bytes: 3008
#include<stdio.h>
 int main(){
  int x,y;
  while(1){
    scanf("%d %d",&x,&y);
    if(x == 0&&y == 0){
      break;
    }else{
      for(int i = 1;i <= x;i++){
        for(int k = 1;k <= y;k++){
          printf("#");
        }
        printf("\n");
      }
      printf("\n");
    }
   
  }
  return 0;
}

Measured memory_bytes: 1796
N = int(input())
AC = 0
WA = 0
TLE = 0
RE = 0
for i in range(N):
  temp = input()
  if temp == 'AC':
    AC += 1
  if temp == 'WA':
    WA += 1
  if temp == 'TLE':
    TLE += 1
  if temp == 'RE':
    RE += 1
print('AC x {}'.format(AC))
print('WA x {}'.format(WA))
print('TLE x {}'.format(TLE))
print('RE x {}'.format(RE))

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

int main(){
string n ;
cin >>n;
if (n[0]=='7'||n[1]=='7'||n[2]=='7') cout <<"Yes"<<endl;
else cout<<"No"<<endl;
}

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

#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//以降 cin の入力元が 'input.txt' になる
//std::ifstream in("input.txt");
//std::cin.rdbuf(in.rdbuf());


signed main()
{
    gearup;
    int k; cin >> k;
    string s = "ACL";
    rep(i,k)cout << s;
    cout << endl;
}

Measured memory_bytes: 3616
/*                          The four Truths of Life

                                    CKMKB
                                    PKMKB

                                    CKMKC
                                    PKMKC
*/


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <climits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define ye cout<<"YES";
#define no cout<<"NO";
#define ln cout<<"\n";
// cout<<"Case #"<<ts<<": “;
//priority_queue < pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;


using namespace std;

ll mod(ll x, ll m) {
	return (x % m + m) % m;
}

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

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ll t = 1, r, n, a, d, c, b, x, y, sum, cnt, i, j, k, m, l, q, maxx, minn, temp, ans, flag, g, ts;
	ll mod = 1000000007;
	char ch, chh;
	double dans;
	string str, ttr;
//cin >> t;


	for (ts = 1; ts <= t; ts++)
	{
		flag = 0; sum = 0; cnt = 0; ans = 0; k = 0; maxx = 0; minn = 0; a = 0; b = 0; temp = 0;

		cin >> n;
		//ll arr[n]; for (i = 0; i < n; i++) {cin >> arr[i];}

		if (n % 1000 == 0)
			cout << 0;
		else
			cout << (1000 - (n % 1000));






		ln
	}
	return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, a, ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a;
		if (i * a % 2) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3636
package main

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

func getNextLine(scanner *bufio.Reader) string {
	var buffer string
	for {
		line, isPrefix, _ := scanner.ReadLine()
		buffer += string(line)
		if isPrefix == false {
			break
		}
	}
	return buffer
}

func getIntList(scanner *bufio.Reader) []int {
	list := strings.Split(getNextLine(scanner), " ")
	l := len(list)
	result := make([]int, l)
	for i := 0; i < l; i++ {
		result[i], _ = strconv.Atoi(list[i])
	}
	return result
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := bufio.NewReader(fp)

	var n, m int

	fmt.Sscan(getNextLine(scanner), &n, &m)

	ans := 1
	for m > 1 {
		cnt := 0
		for i := 2; i <= m/2; i++ {
			if m%i != 0 {
				continue
			}
			for m%i == 0 {
				m = m / i
				cnt++
			}
			ans *= chokudai(cnt, n)
			ans = mint(ans)
			break
		}
		if cnt == 0 {
			ans *= chokudai(1, n)
			ans = mint(ans)
			break
		}
	}
	fmt.Println(ans)
}
func mint(a int) int {
	return (a + 1000000007) % 1000000007
}

func chokudai(a int, b int) int {
	dp := make([][]int, a+1)
	for i := 0; i <= a; i++ {
		dp[i] = make([]int, b+1)
	}
	for i := 0; i <= b; i++ {
		dp[0][i] = 1
	}
	for i := 1; i <= a; i++ {
		for j := 1; j <= b; j++ {
			dp[i][j] += dp[i-1][j] + dp[i][j-1]
			dp[i][j] = mint(dp[i][j])
		}
	}
	return dp[a][b]
}


Measured memory_bytes: 25472
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
/*
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { return MUL(x, POW(y, MOD-2)); }
*/

int
main(void){  
  int n, k;
  cin >> n >> k;
  int d[k] = {};
  REP(i, k) {
    cin >> d[i];
  }
  int val = 0;
  FOR(i, n, INT_MAX){
    bool f = false;
    val = i;
    while(val > 0){
      int temp = val % 10;
      REP(j, k){
	if(temp == d[j]) f = true;
      }
      val = val / 10;
    }

    if(!f){
      cout << i << endl;
      break;
    }

  }

  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = 1 << 28;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    vl x(n), y(n), z(n);
    vvl xyz(8, vl(n, 0));
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> z[i];
        for (int j = 0; j < 8; ++j) {
            if (1 << 0 & j)
                xyz[j][i] += x[i];
            else
                xyz[j][i] -= x[i];
            if (1 << 1 & j)
                xyz[j][i] += y[i];
            else
                xyz[j][i] -= y[i];
            if (1 << 2 & j)
                xyz[j][i] += z[i];
            else
                xyz[j][i] -= z[i];
        }
    }
    for (int i = 0; i < 8; ++i) {
        sort(xyz[i].begin(), xyz[i].end(), greater<ll>());
    }
    ll ret = 0;
    for (int i = 0; i < 8; ++i) {
        ll temp = 0;
        for (int j = 0; j < m; ++j) {
            temp += xyz[i][j];
        }
        chmax(ret, temp);
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 384
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<functional>
#include<random>
#include<unordered_set>
using namespace std;
typedef long long int llint;
#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
const int mod=1000000007;
const int big=1e8+10;
const long double pai=3.141592653589793238462643383279;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
int gcd(int a,int b){if(a%b==0){return b;}else return gcd(b,a%b);}//a>b
int main(void){
	llint n,i,ans=1;cin>>n;
	vector<int> taka(n+2);
	vector<int> ao(n+2);
	for(i=1;i<=n;i++){cin>>taka[i];}taka.back()=taka[n];
	for(i=1;i<=n;i++){cin>>ao[i];}ao[0]=ao[1];
	if(taka[n]!=ao[1]){cout<<0<<endl;return 0;}
	int mata=0,mao=n+2;
	for(i=1;i<=n;i++){
		if(taka[i-1]<taka[i]){mata=i;}
		if(ao[i]>ao[i+1]&&mao==n+2){mao=i;}
		if(taka[i-1]<taka[i]||ao[i]>ao[i+1]){continue;}
		ans*=min(taka[i],ao[i]);
		ans%=mod;
	}
	if(mao<mata){cout<<0<<endl;return 0;}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;

#define MAX 100

struct info{
  int g, t;
  info(int g, int t) : g(g), t(t) {}
};

int arr[MAX];
vector<info> seat;

int minite(int i){
  return 17*(i%2) + 3*(i%3) + 19;
}

void make(){
  int g = 0;
  for(int i = 0 ; i < 17 ; i++){
    seat.push_back(info(-1,-1));
  }
  vector<info> _wait;
  for(int i = 0 ; i < 570 ; i++){
    int size = _wait.size();

    if(size){
      for(int j = 0 ; j < size ; j++){
        _wait[j].t++;
      }
    }
   
    for(int j = 0 ; j < 17 ; j++){
      if(seat[j].g != -1){
        seat[j].t--;
        if(seat[j].t == 0){
          seat[j].g = seat[j].t = -1;
        }
      }
    }
 
    if(size){
      for(int j = 0 ; j < size ; j++){
        int n = _wait[j].g;
        int cnt, c;
        bool flg = false;
        if(n % 5 == 1) cnt = c = 5;
        else cnt = c = 2;
        for(int k = 0 ; k < 17 ; k++){
          if(seat[k].g == -1) cnt--;
          else cnt = c;
          if(cnt == 0){
            for(int l = k-c+1 ; l <= k ; l++){
              seat[l].g = n;
              seat[l].t = minite(n);
            }
            arr[n] = _wait[j].t;
            flg = true;
            j--;
            _wait.erase(_wait.begin());
            break;
          }
        }
        if(!flg || !_wait.size()) break;
      }
      size = _wait.size();
    }
    if(g == 100) continue;
    if(i % 5 == 0){
      int cnt, c;
      bool flg = false;
      if(size){
        _wait.push_back(info(g,0));
        g++;
        continue;
      }
      if(g % 5 == 1) cnt = c = 5;
      else cnt = c = 2;
      
      for(int j = 0 ; j < 17 ; j++){
        if(seat[j].g == -1) cnt--;
        else cnt = c;
        if(cnt == 0){
          flg = true;
          for(int k = j-c+1 ;  k <= j ; k++){
            seat[k].g = seat[k].g = g;
            seat[k].t = seat[k].t = minite(g);
          }
          arr[g] = 0;
          break;
        }
      }
      if(!flg){
        _wait.push_back(info(g,0));
      }
      g++;
    }
  }
}

int main(){
  int N;

  make();
  while(cin >> N){
    cout << arr[N] << endl;
  }

  return 0;
}

Measured memory_bytes: 1200
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    n <- getInt
    as <- getIntList
    let z = 0 `elem` as
        m = length $ filter (< 0) as
        p = map abs as
        ans | z || even m = sum p
            | odd m = sum p - 2 * (minimum p)
    print ans

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

using namespace std;

map<long long, long long> facts;

long long factor(long long a) {
    long long i, sq;
    if(a % 2 == 0) {
        facts[2]++;
        return factor(a / 2);
    }
    sq = sqrt(a);
    for(i = 3; i <= sq; i+=2) {
        if(a%i==0) {
            facts[i]++;
            return factor(a/i);
        }
    }
    if(a != 1) {
        facts[a]++;
    }
    return 0;
}

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

    factor(n);

    long long result = 0;
    auto begin = facts.begin(), end = facts.end();
    for(auto iter = begin; iter != end; iter++) {
        long long val = iter->second;
        long long i;
        for(i = 1; val > 0; i++) {
            val -= i;
            if(val < 0) break;
        }
        result += (i-1);
    }

    cout << result << endl;
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e5+5;

int main()
{
    LL N;
    while(scanf("%lld",&N)!=EOF)
    {
        LL h,n,t1,t2;
        bool flag=false;
        for(h=1;h<=3500;h++)
        {
            for(n=1;n<=3500;n++)
            {
                t1=N*h*n;
                t2=4*h*n-n*N-h*N;
                if(t1>0&&t2>0&&t1%t2==0)
                {
                    printf("%lld %lld %lld\n",h,n,t1/t2);
                    flag=true;
                    break;
                }
            }
            if(flag) break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>
#include<unistd.h>
#include <array>
#include <map> 
#define ALL(a)  (a).begin(),(a).end()



using namespace std;
typedef long long ll;
struct point{
  int x;
  int y;

};
int gcd(int a, int b)
{
	return a == 0 ? b : gcd(b % a, a);
}
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}

int moji(char in)
{
    int ans = (int)in-(int)'a';
    if((ans < 0) || (ans > 25)){
        ans = 26;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}

int binary_searchh(long long x,long long k[],int n){
  int l=0;
  int r=n;
  while(r-l>=1){
    int i=(l+r)/2;
    if(k[i]==x)return i;
    else if(k[i]<x)l=i+1;
    else r=i;
  }
  return -1;
}

struct File {
    int aa;
    int bb;

    File(const int& aa, const int& bb)
        : aa(aa), bb(bb) {}
};

bool operator<(const File& a, const File& b)
{
    // ファイル種別、ファイル名の順番で優先順位を付けて比較
    return std::tie(a.aa, a.bb) < std::tie(b.aa, b.bb);
}

long long kaijo(long long x){
  long long l=10*10*10*10*10*10*10*10*10+7;
  long long sum=1;
  for(int i=x;i>0;i--){
    sum*=i;
    if(sum>l){
      sum%=l;
    }
  }
  return sum;
}






int main(){
  int N,P;
  cin>>N>>P;
  int A[N];
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  for(int i=0;i<N;i++){
    A[i]%=2;
  }
  long long zero=0;
  long long ichi=0;
  for(int i=0;i<N;i++){
    if(A[i]%2==0){
      zero++;
    }else{
      ichi++;
    }
  }
  if(ichi==0){
    if(P==0){
      long long x=1;
      for(int i=0;i<zero;i++){
        x*=2;
      }
      cout<<x<<endl;
    }else{
      cout<<0<<endl;
    }
  }else{
    long long x=1;
      for(int i=0;i<N-1;i++){
        x*=2;

  }
  cout<<x<<endl;}
  
  
}





  

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

namespace C_ABC136
{
    class MainClass
    {

        static int[] n;
        static long[] s;

        public static void Main(string[] args)
        {
            n = Array.ConvertAll(ReadLine().Split().ToArray(), int.Parse);

            s = Array.ConvertAll(ReadLine().Split().ToArray(), long.Parse);

            for(int i =n[0]-1;i>0;i--){
                long now = s[i];
                long next = s[i-1];
                long diff = now -next;
                if(diff<-1){
                    WriteLine("No");
                    return;
                }else if (diff==-1){
                    s[i-1]--;
                }
            }
            WriteLine("Yes");

        }
    }
}


Measured memory_bytes: 30172
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

const ll INF = 1001001001;

void Main(){
    int n; cin >> n;

    vll a(n); 
    ll tot = 0;
    ll mn = INF;
    int cnt = 0;
    int cnt0 = 0;
    
    rep(i, n) {
        cin >> a[i];
        if(a[i] < 0) cnt++;
        tot += abs(a[i]);
        mn = min(mn, abs(a[i]));        
    }
    
    if(cnt % 2) tot -= 2*mn;   
    cout << tot << endl;
    return;
}

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

Measured memory_bytes: 3932
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#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 <cstring>
#include <limits>
#include <iomanip>

using namespace std;
long long dp[22][1<<21];

int main(){
  int N;
  cin >> N;
  int a[N][N];
  for(int i=0;i<N;i++)for(int j=0; j<N;j++){
     cin >> a[i][j];
  }
  for(int i = 0 ; i <=N; i++){
     for(int j = 0 ; j <(1<<N); j++){
        dp[i][j] = 0;
     }
  }
  dp[0][0]=1;
  int mod = 1000000007;
  for(int i = 0 ; i<N; i++){
     for(int j = 0 ; j <(1<<N); j++){
        if(dp[i][j]!=0){
           //cout << i <<", "<< j <<": " << dp[i][j] << endl;
           for(int k = 0 ; k < N; k++){
              if( a[i][k] == 0 ) continue;
              int j2 = j|(1<<k);
              if(j!=j2){
                 dp[i+1][j2]+=dp[i][j];
                 dp[i+1][j2]%=mod;
              }
           }
        }
     }
  }
  cout << dp[N][(1<<N)-1]<<endl;
  return 0;
}


Measured memory_bytes: 360704
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> vec(n,0);
  REP(i,2*m) {
    int a;
    cin >> a;
    vec[a-1]++;
  }
  REP(j,n) cout << vec[j] << endl;
  return 0;
}
//templete by private_yusuke

Measured memory_bytes: 256
a, b = map(int, input().split())


while b:
    a, b = b, a % b

# aが最大公約数になっている

if a == 1 :
    print(1)
else :
    def factorization(a):
        arr = []
        temp = a
        for i in range(2, int(-(-a**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

        if temp!=1:
            arr.append([temp, 1])

        if arr==[]:
            arr.append([a, 1])

        return arr

    print(int(len(factorization(a)) + 1))

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

using namespace std;

#define pb push_back
#define pf push_front
#define mp make_pair
#define popb pop_back
#define popf pop_front
#define all(v) v.begin(),v.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxn = 1e5 + 1;
const ll inf = 2e18, mod = 1e9 + 7;

int n, l[maxn];

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

	cin >> n;
	for (int i = 0; i < 2 * n; i++)
		cin >> l[i];
	sort(l, l + 2 * n);
	ll ans = 0;
	for (int i = 0; i < 2 * n; i += 2)
		ans += min(l[i], l[i] + 1);
	cout << ans << endl;
}

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

int main() {
  string s;
  cin >> s;
  int flag1 = 0, id1 = 0, id2 = 0, flag4 = 1;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'K' && s[i + 1] == 'I' && s[i + 2] == 'H') {
      if (s[i + 3] == 'B') {
        if (s[i + 4] == 'R') {
          flag1 = 1;
          id1 = i;
          id2 = i + 4;
        }
        else if (s[i + 5] == 'R') {
          flag1 = 1;
          id1 = i;
          id2 = i + 5;
        }
      }
      else if (s[i + 4] == 'B') {
        if (s[i + 5] ==  'R') {
          flag1 = 1;
          id1 = i;
          id2 = i + 5;
        }
        else if (s[i + 6] == 'R') {
          flag1 = 1;
          id1 = i;
          id2 = i + 6;
        }
      }
    }
    if (!(s[i] == 'A' || s[i] == 'K' || s[i] == 'I' || s[i] == 'H' || s[i] == 'B' || s[i] == 'R')) {
      flag4 = 0;
    }
  }
  int cnt1 = 0, cnt2 = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'A' && i < id1) {
      cnt1++;
    }
    if (s[i] == 'A' && i > id2) {
      cnt2++;
    }
  }
  int flag2 = 0;
  if (cnt1 <= 1 && cnt2 <= 1) {
    flag2 = 1;
  }
  string t = "KIHBR";
  int flag3 = 1;
  for (int i = 0; i < t.size(); i++) {
    int tmp = count(s.begin(), s.end(), t[i]);
    if (tmp > 1) {
      flag3 = 0;
    }
  }
  if (flag1 && flag2 && flag3 && flag4) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

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

import sys
input=sys.stdin.readline

#普通のUF
#初期値として頂点数(0-indexed)を与える
#計算量改善を行っているので各処理の計算量はO(α(n))(αはアッカーマン関数の逆関数)
#各連結成分に含まれる頂点の個数を求める関数(Count)がある
#重みつきUFやマージテクについては適宜考える(単にこのUFに付け加えるだけではダメなので改めて作成する)

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,m=map(int,input().split())
uf=UnionFind(n+1)
for _ in range(m):
    a,b=map(int,input().split())
    uf.Unite(a,b)
ans=0
for i in range(n):
    ans=max(ans,uf.Count(i))
print(ans)

Measured memory_bytes: 76100
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
#define fix10 cout << fixed << setprecision(10);
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define MOD 1000000007

vector<bool> like2017(100100,true);
vector<bool> prime(100100,true);

void is_prime(){
  prime.at(0) = false;
  prime.at(1) = false;
  rep(i,3) like2017.at(i) = false;
  for(int i=2;i<=100050;i++){
    if(prime.at(i)){
      for(int j=2; i*j<=100050; j++){
        prime.at(i*j) = false;
        like2017.at(i*j) = false;
      }
    }
  }
  for(int i=3;i<=100010;i+=2){
    if(like2017.at(i) && !prime.at((i+1)/2)) like2017.at(i) = false;
  }
  return;
}

int main(){
  int q;
  cin >> q;
  is_prime();
  vi count(100100,0);
  rep(i,100010){
    count.at(i+1) = count.at(i) + like2017.at(i+1);
  }
  rep(i,q){
    int x,y;
    cin >> x >> y;
    cout << count.at(y) - count.at(x-1) << endl;
  }
}


Measured memory_bytes: 1024
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
total=0
for i in range(N):
  total+=B[A[i]-1]
  if i!=0:
    if A[i]==A[i-1]+1:
      total+=C[A[i-1]-1]
print(total)

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

int main() {
	int K,S;
	cin>>K>>S;
	int ans=0;
	rep(i,K+1)rep(j,K+1){
		if(0<=S-i-j&&S-i-j<=K)ans++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256