소심야채

#include using namespace std; const int treeSize = 1>=1){ if(l&1){ maxV = max(maxV,maxTree[l]); minV = min(minV,minTree[l++]); } if(!(r&1)){ maxV = max(maxV,maxTree[r]); minV = min(minV,minTree[r--]); } } return (maxV - minV) > t >> n; fill(minTree, minTree + treeSize*2, INT_MAX); for(int i=0; i> minTree[treeSize + i]; maxTree[treeSize + i] = minTree[treeSize + i]; } for(int i = treeSize-1; i>0;..

#include #include #include #include using namespace std; typedef long long LL; const int MAX_N = 100010; int sqrtN; struct Query { int idx, s, e; bool operator < (Query &x) { if (s / sqrtN != x.s / sqrtN) return s / sqrtN < x.s / sqrtN; return e < x.e; } }; vector query; int arr[MAX_N], cnt[MAX_N*10]; LL ret = 0, ans[MAX_N]; void add(int x) { ret += (LL)(2 * ++cnt[x] - 1)*x; } void sub(int x) { ..

전형적인 knapsack problem 문제이다. #include #include #include #include using namespace std; typedef pair pii; const int MAX_N = 100; const int MAX_T = 10010; int cache[MAX_N][MAX_T]; int n, t; pii test[MAX_N]; //{studyTime, score} int solve(int idx, int time) // idx단원 이후에 얻을수있는 최대점수 { if (idx == n) return 0; int& ret = cache[idx][time]; if (ret != -1) return ret; ret = solve(idx + 1, time); // idx단원 공부..

#include #include #include using namespace std; const int MAX_N = 100 + 5; const int MAX_W = 100100; int main() { int N, K; int W[100100]; int dp[MAX_N][MAX_W]; // dp[i][j] = [0...i]번 배낭을 사용하여 총합무게 j일때 얻을 수 있는 가치의 최댓값 int weight[MAX_N], value[MAX_N]; scanf("%d %d", &N, &K); for (int i = 1; i

https://www.acmicpc.net/problem/10165 [문제조건] 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000), 버스 노선의 수 M(2 ≤ M ≤ 500,000) 각 버스의 노선 [a,b] 단, 0 ≤ a,b ≤ N-1이고 a ≠ b [문제풀이] 조건 a ≠ b 로 인하여 각 버스의 노선 [a,b]를 두 분류로 나눌수가 있다. $$\displaystyle \begin{cases}ab & passZeroZone\end{cases}$$ ZeroZone == [n-1,0] 그룹 A의 특징으로는 (n-1)번과 0번사이 도로를 지나가지 않으며, 그룹 B의 특징으로는 (n-1)번과 0번사이 도로를 무조건 지나간다. 따라서 그룹A는 그룹 B를 포함할수 없는점을 알수가 있으며, 그룹 ..

#include #include #include #include using namespace std; int n; int dp[900][1 n) continue; if (numPos == 0) { if (startNum != numPos) continue; } else if (numPos == 2) { if (startNum == 0 || (startNum == 1 && width[iter] >= 3)) continue; } else { if (startNum != 1 && width[iter] >= 3) continue; } bool isPossible = true; for (int i = 0; i < 4; i++) { if (state & (1

#include #include #include #include using namespace std; const int INF = 987654321; int main() { int m, n; bool isConnected[26][26] = { false, }; scanf("%d %d", &m, &n); for (int i = 0; i < m; i++) { char a, b; getchar(); scanf("%c %c", &a, &b); int s = a - 'a', e = b - 'a'; isConnected[s][e] = true; } for (int k = 0; k < 26; k++) { for (int i = 0; i < 26; i++) { for (int j = 0; j < 26; j++) { i..